571
\$\begingroup\$

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

To post to the sandbox, scroll to the bottom of this page 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, 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
  • Comments addressing specific points mentioned in the proposal
  • 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".

\$\endgroup\$
2
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    Commented May 15 at 14:05
  • \$\begingroup\$ @None1 If you don't get feedback for a while you can ask in the nineteenth byte \$\endgroup\$
    – mousetail
    Commented May 29 at 13:27

4702 Answers 4702

1
3 4
5
6 7
157
6
\$\begingroup\$

Count alternating permutations

\$\endgroup\$
6
\$\begingroup\$

Scribble Pad for Nerds.

Posted Here

\$\endgroup\$
6
  • \$\begingroup\$ I suggest allowing a matrix of characters as output too (relevant meta). Maybe even allow a boolean matrix as output? \$\endgroup\$
    – pajonk
    Commented May 29, 2022 at 17:22
  • \$\begingroup\$ @pajonk Ah yeah, thanks! \$\endgroup\$
    – math scat
    Commented May 30, 2022 at 19:11
  • 1
    \$\begingroup\$ Maybe Give Examples for intersecting lines or diagonal lines? \$\endgroup\$ Commented May 31, 2022 at 0:25
  • \$\begingroup\$ @Nobody finished! \$\endgroup\$
    – math scat
    Commented Jun 3, 2022 at 18:02
  • 1
    \$\begingroup\$ The [6, 4, 2] example is unclear. If each movement draws 2 #s, why are there 7 total #s? I'm guessing that the board begins with 1 # already drawn, and instructions start from there, but this isn't made clear. In fact, if so, the image for the [6, 4, 2] explanation is wrong, as it says "start at the X", when the X is one space too far to the right. Also, I believe you have left and right mixed up with 2 and 6 in the explanation? \$\endgroup\$ Commented Jun 4, 2022 at 18:01
  • \$\begingroup\$ @cairdcoinheringaahing oh frick yeah, I'm gonna fix it later, thanks \$\endgroup\$
    – math scat
    Commented Jun 4, 2022 at 19:31
6
\$\begingroup\$

Create Bernard from Desmos

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Might want to include this animation for understanding the algorithm as listed. However, that algorithm is a bit complicated because it describes the reason for the pattern forming; you could keep it at the end, but I'd suggest describing the result matrix in terms of rectangles: Quadrants 3 and 4 are filled with 1s, as well as quadrant 1.1 and 1.2, then recurse on quadrant 1.4. (where quadrant a.b is the bth quadrant of the ath quadrant, and quadrants are numbered counter-clockwise starting from 1=top right quadrant) \$\endgroup\$ Commented Jun 16, 2022 at 7:15
  • \$\begingroup\$ Please take a screenshot of bernard in case this specific manifestation of the bug is fixed or changed, for posterity \$\endgroup\$ Commented Jun 17, 2022 at 3:43
  • 1
    \$\begingroup\$ @thejonymyster OK will do \$\endgroup\$
    – Aiden Chow
    Commented Jun 20, 2022 at 7:02
6
\$\begingroup\$

Extract the word containing this index

\$\endgroup\$
4
  • \$\begingroup\$ can we take input as list of words? \$\endgroup\$
    – naffetS
    Commented Jun 20, 2022 at 16:02
  • \$\begingroup\$ @Steffan I didn't want to allow that, because it means there are indices that fall on the boundaries of words with no corresponding value, which I think would unnecessarily complicate the rules and confuse the challenge for little benefit. If you can make a good case for why it should be allowed, I'm all ears. \$\endgroup\$
    – pxeger
    Commented Jun 20, 2022 at 16:03
  • 2
    \$\begingroup\$ This is a delightful problem. It seems like it should be trivial, but it's not exactly. And I can think of multiple ways to do it that are competitive with each other in my chosen language. \$\endgroup\$
    – chunes
    Commented Jun 20, 2022 at 19:33
  • 1
    \$\begingroup\$ @chunes Thank you! My favourite challenges are exactly those like this one: despicably simple, with numerous possible approaches. I find the best source of inspiration for these is problems I encounter in real-world programming. \$\endgroup\$
    – pxeger
    Commented Jun 20, 2022 at 20:04
6
\$\begingroup\$

Enumerate the Microwave Timer

\$\endgroup\$
3
  • \$\begingroup\$ Now I wanna try this on my microwave :P \$\endgroup\$
    – Seggan
    Commented Jun 19, 2022 at 1:25
  • \$\begingroup\$ Can the output times be [second, minute]? \$\endgroup\$
    – naffetS
    Commented Jun 20, 2022 at 15:54
  • \$\begingroup\$ @steffan that's covered under the reasonable format rule \$\endgroup\$
    – lyxal
    Commented Jun 21, 2022 at 0:56
6
\$\begingroup\$

Live a longer life

\$\endgroup\$
4
  • \$\begingroup\$ Winning criterion? \$\endgroup\$
    – emanresu A
    Commented Aug 23, 2022 at 0:10
  • \$\begingroup\$ Here are two of my suggestions in chat as a reminder: 1 2 \$\endgroup\$
    – Bubbler
    Commented Aug 26, 2022 at 3:55
  • 1
    \$\begingroup\$ Both \$n=1\$ and \$n=2\$ have better options: [[1]] and [[1,1],[1,0]] (or o! and 2o$o! respectively in RLE format). Both take one generation (instead of zero) to reach a fixed board. \$\endgroup\$
    – alephalpha
    Commented Aug 29, 2022 at 7:08
  • 1
    \$\begingroup\$ If you intend to post both n=1 and 2 yourself, specifically picking p1=0 (empty board) and p2=1 (e.g. a triangle by alephalpha) would be more consistent with the rules. \$\endgroup\$
    – Bubbler
    Commented Aug 30, 2022 at 5:33
6
\$\begingroup\$

Introduction

Raku's sequence operator is very flexible. It does a lot of different things, but for the purposes of this challenge, we'll focus on two particular features:

  • Given two integers, it counts up or down as appropriate. 1 ... 5 => (1, 2, 3, 4, 5); 9 ... 5 => (9, 8, 7, 6, 5).
  • It can occur multiple times in the same expression, and will count up or down from one argument to the next. 4 ... 6 ... 3 ... 1 ... 2 => (4, 5, 6, 5, 4, 3, 2, 1, 2).

Challenge

Write a function that accepts a list of integers (or a number of integer parameters) and returns a list of the integers that would be produced by inserting Raku's sequence operator between the input integers. That is, between each adjacent pair of input numbers a and b, insert an ascending sequence of integers from a + 1 to b - 1 if a < b, and a descending sequence of integers from a - 1 to b + 1 if a > b. But also:

  • If | a - b | == 1, insert nothing between them.
  • If a == b, include just one copy of a in the output list.

Lowest byte count wins. Raku answers which employ the sequence operator are disallowed.

Test Cases

1, 5 -> (1, 2, 3, 4, 5)
20, 17 -> (20, 19, 18, 17)
1, 3, 1 -> (1, 2, 3, 2, 1)
1, 3, 3, 3, 3, 3, 5 -> (1, 2, 3, 4, 5)
5, 4, 6, 3, 7 -> (5, 4, 5, 6, 5, 4, 3, 4, 5, 6, 7)
100, 100, 100, 100 -> (100)
\$\endgroup\$
2
  • \$\begingroup\$ @thejonymyster To me it doesn't look like substantially more background info than many other challenges provide. But perhaps I can pare it down to a few sentences rather than a bulleted list. \$\endgroup\$
    – Sean
    Commented Oct 7, 2022 at 21:46
  • \$\begingroup\$ Consider adding something about permitted IO e.g that default I/O Rules while standard loopholes are forbidden and a winning criterion e.g. this is code-golf, the shortest code in bytes wins. \$\endgroup\$
    – solid.py
    Commented Nov 1, 2022 at 10:39
6
\$\begingroup\$

Fractional Unicode Bars

Your program should take as input a number n and output a bar composed of n // 8 ▉ characters (U+2588), as well as a final character which should be one of ▊ ▋ ▌ ▍ ▎▏(U+2589 to U+258F) representing n % 8. If n % 8 is 0, your program should not output any additional characters. This is difficult to explain well in text, so here are some examples:

Input: 8
Output: ▉
Input: 32
Output: ▉▉▉▉
Input: 33
Output: ▉▉▉▉▏
Input: 35
Output: ▉▉▉▉▍
Input: 246
Output: ▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▉▊

This is , so shortest answer wins.

\$\endgroup\$
6
\$\begingroup\$

Output the ground-state configutation of an element

Task: Given the atomic number as input, output the ground-state electron configuration.

Background info

In each orientation per orbital, there can be at most 2 electrons. Specifically:

  • The s orbital has 1 orientation, so it can be filled with a maximum of 2 electrons.
  • The p orbital has 3 orientations, so it can be filled with a maximum of 6 electrons.
  • The d orbital has 5 orientations, so it can be filled with a maximum of 10 electrons.
  • The f orbital has 7 orientations, so it can be filled with a maximum of 14 electrons.

et cetera.

The orbitals per orbit level are listed like so:

1s
2s 2p
3s 3p 3d
4s 4p 4d 4f
5s 5p 5d 5f ...

Based on the Aufbau priciple, we order the orbitals diagonally, so the energy order of these orbitals is like this:

1s < 2s < 2p < 3s < 3p < 4s < 3d < 4p < 5s < 4d < 5p < ...

The orbitals with higher energy levels are only filled up if all of the lower energy level orbitals are completely filled. Taking Na (atomic number 11) as an example:

1s^2, 2s^2, 2p^6, 3s^1

(2p^6 means there are 6 electrons in the 2p orbital, and so on.)

Finally, we put that in order and output the electrons at the specfied level:

1: 1s^2
2: 2s^2 2p^6
3: 3s^1

So 2, 8, 1 is our output.

Testcases

1 -> [1]
3 -> [2, 1]
9 -> [2, 7]
10 -> [2, 8]
13 -> [2, 8, 3]
21 -> [2, 8, 9, 2]
28 -> [2, 8, 16, 2]
29 -> [2, 8, 18, 1]
34 -> [2, 8, 18, 6]
41 -> [2, 8, 18, 12, 1]
48 -> [2, 8, 18, 18, 2]
115 -> [2, 8, 18, 32, 32, 18, 5]
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I assume the task is: Given the atomic number as input, output the ground-state electron configuration. Is this right? If so, please clarify in the post. \$\endgroup\$ Commented Apr 16, 2023 at 12:10
  • 1
    \$\begingroup\$ @Jacob Yes. I'll add that in the post. \$\endgroup\$
    – user117658
    Commented Apr 16, 2023 at 12:39
  • \$\begingroup\$ You might want to add the test case 46 -> [2, 8, 18, 16, 2] to make clear that we are not considering the actual electron configurations. (Palladium's actual config is [2, 8, 18, 18].) \$\endgroup\$ Commented May 9, 2023 at 6:45
6
\$\begingroup\$

Find the largest sum such that no two elements are touching

\$\endgroup\$
4
  • 2
    \$\begingroup\$ I’d replace the for some k in N MathJax bit with “for some positive integer k”. Personally I don’t think the polynomial time constraint really makes this any more interesting, but it’s your challenge. \$\endgroup\$ Commented Sep 13, 2023 at 12:02
  • \$\begingroup\$ @noodleman Polynomial time prevents solutions that check all subsets \$\endgroup\$
    – bsoelch
    Commented Sep 13, 2023 at 16:56
  • \$\begingroup\$ Actually, your examples contain zero, which is no positive integer. You probably mean non-negative integers? \$\endgroup\$
    – Philippos
    Commented Sep 14, 2023 at 11:29
  • \$\begingroup\$ @Philippos I fixed the example \$\endgroup\$
    – bsoelch
    Commented Sep 14, 2023 at 12:18
6
\$\begingroup\$

Print the answer before a given answer

\$\endgroup\$
15
  • 1
    \$\begingroup\$ I think you should add quine, because you need to output your own source code (although only given a certain input) \$\endgroup\$ Commented Sep 23, 2023 at 4:55
  • \$\begingroup\$ Currently it might make sense for answers to encode the data they are printing somehow (maybe even in a highly language-specific way), so following answers will either have to write their own encoder or duplicate all earlier programs. Is this something you want? \$\endgroup\$ Commented Sep 23, 2023 at 5:08
  • \$\begingroup\$ To clarify my comment: the usual solution would be something like A = 'somecode'; B = 'print({A})'; C = 'print({B})'; ...; Q = quine; arr = [A, B, C, ..., Q]; print(arr[arr.index(input()) - 1 % N]), but if C, for example, has a very weird encoding of B's code, then you couldn't reuse B's code you already produced, and will have to either to write a long encoding code or copy the encoded B, and I'm not sure if this is something you want or not \$\endgroup\$ Commented Sep 23, 2023 at 5:13
  • 1
    \$\begingroup\$ How would this work with languages that use different character encodings, should the program output the same (Unicode) characters or the same sequence of bytes. \$\endgroup\$
    – bsoelch
    Commented Sep 23, 2023 at 8:32
  • 1
    \$\begingroup\$ You should add the first answer as the cat program, so nobody else can do it. \$\endgroup\$ Commented Sep 23, 2023 at 12:45
  • 1
    \$\begingroup\$ @bsoelch That's a good question, I think I'll go with bytes. Since some languages can't do byte I/O directly, they could always just use Unicode chars 0-255 and pretend they're bytes. \$\endgroup\$ Commented Sep 23, 2023 at 13:38
  • 1
    \$\begingroup\$ @TheEmptyStringPhotographer Good point, maybe I will. If one got submitted that was either empty or overly complex, it could break the challenge quite a bit \$\endgroup\$ Commented Sep 23, 2023 at 13:39
  • \$\begingroup\$ why are negative score answers invalid? is this code-shuffleboard :P? my reading is that your score is the percent increase between previous answer and your own... if your code is shorter than previous, that would be a negative percent... whats the big idea :-) \$\endgroup\$ Commented Sep 25, 2023 at 4:05
  • \$\begingroup\$ @thejonymyster If you're score's a negative percent change, that's still valid and treated the same. Didn't think of that case tho, I assume it probably won't happen \$\endgroup\$ Commented Sep 25, 2023 at 21:52
  • \$\begingroup\$ asking because your draft currently explicitly says "Answers with a negative score are invalid", so im not sure what you were trying to get at there, and then there's a clause about how invalid answers can be ignored... seeing as theres no other score modifiers, i have no idea what you intended there. :o might wanna read the whole thing over one more time \$\endgroup\$ Commented Sep 25, 2023 at 22:04
  • 1
    \$\begingroup\$ @thejonymyster Ohhh I meant negative score as in votes. So if someone does something annoying, you can downvote their answer enough to invalidate it \$\endgroup\$ Commented Sep 25, 2023 at 22:07
  • \$\begingroup\$ Ahhh lmao ok that also explains why you referenced "score" before giving the "scoring" rule. your edit clears it up. good mechanic btw \$\endgroup\$ Commented Sep 25, 2023 at 22:13
  • 2
    \$\begingroup\$ If negative-voting answers are invalid, I could just downvote a new answer to allow me to take it’s place. This doesn’t seem fair. I suggest doing something like -3 or lower to be invalid. \$\endgroup\$ Commented Sep 27, 2023 at 18:51
  • \$\begingroup\$ Also, am I allowed to use open(__file__).read() to get the source code? \$\endgroup\$ Commented Sep 27, 2023 at 18:57
  • \$\begingroup\$ @TheEmptyStringPhotographer No, I'll clarify no reading source code or external resources is allowed \$\endgroup\$ Commented Sep 27, 2023 at 19:06
6
\$\begingroup\$

Minimum Escaping

Your task is to write 2 functions/programs. They may share code.

The first function must, given a string and a character, output a new string that does not contain that character.

The second function must, given the string from the previous function and the excluded character, reconstruct the original string.

All input strings will be ASCII printable, all output strings must be ASCII printable. You may choose to include or exclude whitespace.

Examples

One could try to use replace the character with an escape sequence. For example \#bcda with excluded character becomes \\#bcd\# then you'd know to replace \# with whatever character is excluded. However, the excluded character might itself be # or \ so if one uses this method they'd need to be able to dynamically switch to a different escape sequence in that case.

There is no length limit for the censored string so you could try to encode the entire string in unary, but be careful that the unary char you choose may not be the excluded char.

This is code golf, shortest answer in each language wins. Brownie points for interesting solutions even if they are not the shortest though.

\$\endgroup\$
6
\$\begingroup\$

Display integer in balanced base-ϕ

Objective

Given a positive integer, display it in balanced base-ϕ numeral. ϕ is the golden ratio.

Balanced base-ϕ

Unlike the usual base-ϕ that uses 0 and 1 as digits, balanced base-ϕ uses 1 and -1 as digits.

-1 is written T as a shorthand.

To ensure uniqueness of the representation, there are some restrictions:

  • 1TT cannot appear anywhere (while the radix point is ignored). To get rid of it, it can be replaced by T11.

  • The least significant digit must be 1.

Even with these restrictions, there still is an integer whose representation isn't unique, namely 2. For the purpose of this challenge, you can output either 1T1 or 1.11.

Rules

Note that I haven't proven that a balanced base-ϕ representation exists for every positive integer. I doubt there is an integer without a balanced base-ϕ representation, but such input shall result in don't care situation.

Also note that I haven't proven that 2 is the only positive integer with ambiguous balanced base-ϕ representation. Just in case another integer with ambiguous representation is inputted, output anything amongst such representations.

Examples

Decimal, Balanced base-ϕ
1, 1
2, 1T1 or 1.11
3, 1T1.11
4, 11.1111
5, 111.T1
6, 111.1T1111
7, 11T1.1T1111
8, 1T111.T111
9, 111T.111111
10, 1111.1T1T1111
11, 1111.111111
12, 1T11T1.111111
13, 1T111T.111T1111
14, 1T1111.T11111
15, 1T1111.111T1111
16, 11111.T1T1
17, 11T1T1.111T1111
18, 11T11T.11T111
19, 1T11.11T111
20, 11T111.11T111
\$\endgroup\$
2
  • 2
    \$\begingroup\$ To prove this covers all numbers you can probably use the fact that every integer has a representation as a sum of distinct Lucas numbers, and the formula \$L_n = \phi^n + (-\phi)^{-n}\$. \$\endgroup\$ Commented Dec 15, 2023 at 10:47
  • 1
    \$\begingroup\$ Funny! I just added base conversion to my language and thought: Why restrict it to integer bases? Now I come back and see this challenge! I found a challenge about base conversion with float numbers, but none with float base so far (or did I miss it?). Should this maybe be first before getting more complicated with balanced base? \$\endgroup\$
    – Philippos
    Commented Dec 17, 2023 at 18:04
5
\$\begingroup\$

I attempted a problem I threw out as a suggested 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'.
\$\endgroup\$
11
  • \$\begingroup\$ The program should take it's input from the standard input or by reading a file called "makefile" - is this a choice for the implementer to make? Or should the program read stdin, and if it's empty then look for makefile? 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 before execution of any rules. Does "generate an error" include aborting, such that no rules are executed? Running each in sequence - missing "action"? Why is the sample input indented? I'll do an edit for punctuation in a bit. \$\endgroup\$ Commented May 20, 2011 at 21:36
  • \$\begingroup\$ In order. (1) Implementer's choice. Should be more specific. (2) Generate an error means abort; this is a unix utility after all. (3) The sample is indented because I made a strenuous effort to get the tabs in, and MarkDown just doesn't like tabs. Also there is a new sample input that has some comments in. \$\endgroup\$ Commented May 20, 2011 at 21:49
  • \$\begingroup\$ More questions: 1) The target is "newer" than the prerequisite once *they* have been fulfilled. What does this mean? Should this text be talking about building? 2) Under what circumstances can a target be built twice? \$\endgroup\$ Commented May 21, 2011 at 19:51
  • \$\begingroup\$ 1) Yes and 2) Standard make never builds a target twice, and neither does my reference implementation. But I should probably say that it is or is not allowed. Do you have a feeling in the matter? \$\endgroup\$ Commented May 21, 2011 at 20:43
  • \$\begingroup\$ Saying that it is not allowed is probably best. Otherwise there's potential for stuff to go wrong when multiple targets depend on clean, which will never be built because it doesn't correspond to a file. \$\endgroup\$ Commented May 21, 2011 at 21:15
  • 1
    \$\begingroup\$ I suggest that the golf exercise be to simply output the list of commands to run, not actually execute them. Will make testing much easier. \$\endgroup\$ Commented May 27, 2011 at 0:50
  • \$\begingroup\$ This is awesome. But I'm too mystified by make to even fathom how it goes about it. I'd never be able to do this without stealing ideas from other posts on the page. But then, I'm an introverted intuitive, intellectuals would probbly have an easier time. :) I haven't checked, but .. I say it's ready to post. Answers may be slow in coming, but they WILL come! \$\endgroup\$ Commented Nov 23, 2012 at 4:45
  • \$\begingroup\$ @luserdroog my reference implementation builds a directed graph (in the technical sense) of dependencies and then starts evaluating from the named target(s). I can't recall right off if I enforced acycality on the graph or not. I believe that real make insists on it. \$\endgroup\$ Commented Nov 23, 2012 at 5:10
  • \$\begingroup\$ That doesn't semm quite so unfathomable. I suppose the variables and impicit rules are responsible for much of the mystery. \$\endgroup\$ Commented Nov 23, 2012 at 5:45
  • \$\begingroup\$ This has been inactive for five years. If you're not going to post it, may I? \$\endgroup\$
    – MD XF
    Commented Aug 17, 2017 at 16:59
  • \$\begingroup\$ @MDXF I think I'd rather post this one myself, but it may be a few days. \$\endgroup\$ Commented Aug 17, 2017 at 19:51
5
\$\begingroup\$

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.


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.

\$\endgroup\$
0
5
\$\begingroup\$

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.

\$\endgroup\$
12
  • \$\begingroup\$ Oops, didn't see that, sorry :S I think there might be problems still, as several moves could be hard-coded in. (i.e. the first move(s) is always just the middle column) \$\endgroup\$ Commented Feb 4, 2015 at 17:07
  • \$\begingroup\$ @FryAmTheEggman I am totally fine with a few hard coded moves, but perhaps I should reintroduce the byte limit that I originally had in place. Do you think 500 characters is sufficient? I went ahead and added it back. I also added a restriction on external resources to prevent external hard coding. It's probably a loophole, but one worth covering I think. (I'm in chat btw if you want to discuss.) \$\endgroup\$
    – Rainbolt
    Commented Feb 4, 2015 at 17:08
  • \$\begingroup\$ 500 seems fine, but it might squeeze Java / C# entries. I'll see how long a pretty bad bot is over the weekend if you haven't posted yet ;p \$\endgroup\$ Commented Feb 4, 2015 at 17:21
  • \$\begingroup\$ @FryAmTheEggman It will be a little while. I haven't written the controller yet. Thanks for the feedback! \$\endgroup\$
    – Rainbolt
    Commented Feb 4, 2015 at 17:25
  • \$\begingroup\$ I took a program that claims to do perfect play and added some timing: the vast majority of its moves take less than 1ms; in about 1 game in 8 it has a single move which takes more than 1s. The longest I've seen was just short of 2s, so with a bit of optimisation and a more modern computer it might well come inside the 1s limit. The byte limit would hit it hard, though: its opening book is 12k. \$\endgroup\$ Commented Feb 4, 2015 at 20:14
  • \$\begingroup\$ @PeterTaylor Thank you for that. Knowing what you just found out, do you think that the 500 byte limit plus the timing restriction are enough to make the challenge interesting? If someone can solve Connect Four optimally under those restrictions, then at least PPCG has created something worth having, right? I'm just asking because nobody has upvoted the sandbox proposal, so I assume that maybe there are still some concerns about it. \$\endgroup\$
    – Rainbolt
    Commented Feb 4, 2015 at 20:37
  • \$\begingroup\$ I got distracted by looking for work on perfect play and didn't post the thoughts I had. I'm slightly confused about the input format: is \n a literal backslash followed by an n, or does it mean a newline character? The latter would be my assumption, but the example input makes it look literal (and wouldn't work if it were newline). I don't think you specify whether the output assumes 0-indexed or 1-indexed columns. I'm not sure whether the rule about external resources is intended to indicate that I can fetch stuff from the web without it counting towards the byte limit. \$\endgroup\$ Commented Feb 4, 2015 at 21:18
  • \$\begingroup\$ I feel that with a strict byte limit, you're most likely to see mainly versions of min/max or other "simple" algorithms. If you want more interesting or varied players, you may want to relax it. Banning extensive hard-coding is good, but I'd hate for it to come at the expense of creativity. \$\endgroup\$
    – Geobits
    Commented Feb 4, 2015 at 21:19
  • \$\begingroup\$ The byte limit and timing restriction between them may be too much: I can't see any approach which attempts a real analysis fitting into 500 bytes except in a golfing language which will struggle with the time limit. Maybe 2kB would be a better compromise. \$\endgroup\$ Commented Feb 4, 2015 at 21:20
  • \$\begingroup\$ @PeterTaylor 2000 bytes it shall be, then. I changed the row delimiter to ; to eliminate confusion. I added that columns are zero indexed. The rule about external resources was intended to allow you to fetch from existing resources, but to disallow you to fetch from resources that were created after the fact. In hindsight, this might open the door to abuse, so I've removed that allowance. I'm unsure if this leaves the challenge vulnerable or not, so I'll bring it up in chat. \$\endgroup\$
    – Rainbolt
    Commented Feb 4, 2015 at 21:28
  • \$\begingroup\$ Discussed in chat and made the change. I think I've addressed all comments up to now. \$\endgroup\$
    – Rainbolt
    Commented Feb 4, 2015 at 21:38
  • \$\begingroup\$ I didn't look very closely at that command line. It should be java MyBot (or maybe java -classpath c:\ MyBot, not java C:\MyBot.java. Other that that, looks good. \$\endgroup\$ Commented Feb 4, 2015 at 22:40
5
\$\begingroup\$

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

enter image description here

\$\endgroup\$
18
  • 7
    \$\begingroup\$ 2. Lego pieces/attachable cubes \$\endgroup\$ Commented Jan 25, 2015 at 21:07
  • 2
    \$\begingroup\$ 5. Controller-mediated build-your-own data structure \$\endgroup\$ Commented Jan 25, 2015 at 21:11
  • \$\begingroup\$ A. Lego pieces. \$\endgroup\$ Commented Jan 28, 2015 at 8:35
  • 6
    \$\begingroup\$ B. Attachable unit cubes (for simplicity) \$\endgroup\$ Commented Jan 28, 2015 at 8:36
  • \$\begingroup\$ Winning criteria: \$\endgroup\$
    – Sp3000
    Commented Jan 28, 2015 at 23:43
  • 2
    \$\begingroup\$ I. Code golf (fewest bytes) \$\endgroup\$
    – Sp3000
    Commented Jan 28, 2015 at 23:43
  • 7
    \$\begingroup\$ II. Fastest algorithm \$\endgroup\$
    – Sp3000
    Commented Jan 28, 2015 at 23:44
  • \$\begingroup\$ III. Something else (leave a comment below) \$\endgroup\$
    – Sp3000
    Commented Jan 28, 2015 at 23:45
  • 1
    \$\begingroup\$ Number of cube structures: \$\endgroup\$
    – Sp3000
    Commented Jan 29, 2015 at 0:42
  • \$\begingroup\$ 1. Exactly one structure \$\endgroup\$
    – Sp3000
    Commented Jan 29, 2015 at 0:42
  • 3
    \$\begingroup\$ 2. Any number of structures \$\endgroup\$
    – Sp3000
    Commented Jan 29, 2015 at 0:43
  • \$\begingroup\$ Connections/adjacency: \$\endgroup\$
    – Sp3000
    Commented Jan 29, 2015 at 0:43
  • 3
    \$\begingroup\$ A. Connections should be explicitly given via a function call \$\endgroup\$
    – Sp3000
    Commented Jan 29, 2015 at 0:44
  • \$\begingroup\$ B. Each cube is connected to the cube it was built off \$\endgroup\$
    – Sp3000
    Commented Jan 29, 2015 at 0:45
  • 2
    \$\begingroup\$ Moving to 2D might simplify rotations greatly, while retaining enough complexity to be worth a challenge. \$\endgroup\$
    – user16991
    Commented Feb 5, 2015 at 1:49
5
\$\begingroup\$

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.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Could you give a more precise definition of 'most likely'? \$\endgroup\$
    – feersum
    Commented Jun 7, 2015 at 21:30
  • \$\begingroup\$ If two family trees are equally likely, can either be output, or would you prefer a rule to specify which one must be output? \$\endgroup\$ Commented Jun 7, 2015 at 22:18
  • \$\begingroup\$ Would it be interesting to have the 25% probability provided as an input p, or would keeping the parameter fixed allow for more golfing opportunities? \$\endgroup\$ Commented Jun 7, 2015 at 22:20
  • \$\begingroup\$ @feersum I'm not sure what you mean. Highest probability? Least improbable? \$\endgroup\$
    – Sparr
    Commented Jun 8, 2015 at 2:45
  • \$\begingroup\$ @trichoplax I hadn't considered that. I guess I'd accept either. I'll mention that. The probability in the original question was 20%, but I think a non-repeating decimal in base 2 will be much more golf-friendly. \$\endgroup\$
    – Sparr
    Commented Jun 8, 2015 at 2:46
  • 1
    \$\begingroup\$ With respect to @feersum's question, I see at least two subtleties. Firstly, what assumption should be made about the distribution of the initial bitstring? Secondly, the "family tree" isn't in bijection with the sequence of random selections. The first one needs to be addressed explicitly; the second is probably best addressed with a worked example which calculates the probabilities for each possible sequence and then sums them over the family tree corresponding to each sequence. As an additional point, an important corner case will be one where the bitstrings aren't all distinct. \$\endgroup\$ Commented Jun 9, 2015 at 11:22
  • \$\begingroup\$ @PeterTaylor The initial bitstring is a sequence of bits chosen independently and uniformly at random. I am unclear on your second point. Do you mean that it's possible for the family tree produced at random to not be the one most likely to have produced a given result set? That makes sense, but seems obvious. I can work out the 4x4 example by hand with probabilities for each of the 6 possible family trees, if that would clarify things? \$\endgroup\$
    – Sparr
    Commented Jun 10, 2015 at 15:44
  • \$\begingroup\$ I agree that it's obvious, but it is often a good idea to state the obvious, because otherwise it can be overlooked. For example, it's also obvious that the 4x4 example must have more than 4! = 24 possible family trees... (I think it's 64 possible trees, so maybe that was just a typo). \$\endgroup\$ Commented Jun 10, 2015 at 16:28
5
\$\begingroup\$

The Virtual Prisoners

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?
\$\endgroup\$
10
  • \$\begingroup\$ I have a few questions. 1) If I make a new node, will it be neutral? 2) How are the matches organized? If there are, say, 5 submissions, does each pair have a separate battle, after which you count victories, or do they somehow work in teams (as the title suggests)? 3) With some strategies it may be that the game runs forever. You should probably add a time limit (some N turns), after which the game automatically ends in a draw, or a win for the player controlling the most nodes. \$\endgroup\$
    – Zgarb
    Commented Apr 7, 2015 at 15:38
  • \$\begingroup\$ @Zgarb Thanks for your feedback! I've included a section on how the game works. \$\endgroup\$ Commented Apr 7, 2015 at 15:53
  • \$\begingroup\$ Could you add C# (or .NET in general?) \$\endgroup\$ Commented Apr 7, 2015 at 15:55
  • \$\begingroup\$ @LegionMammal978 How do you install that on Linux? The list is mostly because I can't run a lot of things like GolfScript, but I'd be glad to, if you can tell me where to find it. \$\endgroup\$ Commented Apr 7, 2015 at 15:56
  • \$\begingroup\$ @ASCIIThenANSI you could use Mono. I'm mainly just looking for C#. \$\endgroup\$ Commented Apr 7, 2015 at 16:02
  • \$\begingroup\$ @LegionMammal978 Oh, OK. Turns out I installed it for an earlier purpose, thanks for your help! \$\endgroup\$ Commented Apr 7, 2015 at 16:09
  • 1
    \$\begingroup\$ It's not complete, but this question has instructions for running a number of languages. \$\endgroup\$ Commented Apr 15, 2015 at 22:15
  • \$\begingroup\$ @PeterTaylor Thanks for the link! \$\endgroup\$ Commented Apr 16, 2015 at 12:57
  • \$\begingroup\$ Maybe add a clock time limit for each turn, so bots don't simply run an endless loop blocking you running the simulation? \$\endgroup\$ Commented Oct 11, 2015 at 8:33
  • \$\begingroup\$ @PaŭloEbermann I'll watch each of the simulations (with output on what the bots are doing), and any bot that takes too long is disqualified. \$\endgroup\$ Commented Oct 12, 2015 at 14:04
5
\$\begingroup\$

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

Golf the numbers round a dartboard

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

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.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ I like the restricted source version \$\endgroup\$
    – quintopia
    Commented Dec 9, 2015 at 19:16
  • 1
    \$\begingroup\$ @TimmyD Link added. I'm surprised we don't have an OEIS tag - I guess it wouldn't really add much. \$\endgroup\$ Commented Dec 9, 2015 at 20:18
  • 1
    \$\begingroup\$ @ quintopia - yes, I think that's probably the way to go - edited. \$\endgroup\$ Commented Dec 9, 2015 at 20:19
  • 1
    \$\begingroup\$ I was able to do this in CJam in 26 bytes using character to int conversion (it only didn't work online for 13 because it's character is carriage return.) Should this be allowed? goo.gl/JxEcjo . Also, in CJam 1,2,3 and 10-20 are single letter constants. Should those be allowed? \$\endgroup\$
    – geokavel
    Commented Dec 10, 2015 at 5:58
  • 1
    \$\begingroup\$ @geokavel yes, and yes. \$\endgroup\$ Commented Dec 10, 2015 at 6:16
  • 2
    \$\begingroup\$ This is just asking for string compression, especially since digits can't be used even indirectly. \$\endgroup\$
    – xnor
    Commented Dec 10, 2015 at 19:32
  • \$\begingroup\$ @xnor to discourage that, maybe restrict entries to printable ASCII (or give a bonus of *log 95/log 256 for using only printable ASCII)? \$\endgroup\$
    – lirtosiast
    Commented Dec 10, 2015 at 23:40
5
\$\begingroup\$

Verify a game of Morpion Solitaire

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:

enter image description here

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:

enter image description here enter image description here enter image description here
enter image description here enter image description here enter image description here

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:

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 rules apply.

Sandbox Notes

  • Will add test cases...
\$\endgroup\$
8
  • \$\begingroup\$ The simplest representation for parsing would be to give either the endpoints of each line as cartesian coordinates, or one endpoint and a direction (either one of 8 directions, or it could be standardized to one of 4 directions if the N/E/NE/NW is always the endpoint given.) Checking would then be fairly straightforward: start with the empty grid and see which lines are allowed, until all are exhausted. \$\endgroup\$ Commented Dec 21, 2015 at 9:34
  • \$\begingroup\$ The ASCII art representation will require more effort for parsing: I think it's unambiguous because you can identify endpoints by looking for for intersections which don't have opposite pairs of |_\/, but it could take quite a few parses through the file. You would also need some way of identifying the start points. \$\endgroup\$ Commented Dec 21, 2015 at 9:35
  • \$\begingroup\$ @steveverrill There will be no information about endpoints in the input. In a finished game (without numbering) you only have individual line segments (four of which make up a move). That's why I think an ASCII representation is simpler than a graph, where you need to piece together manually which edges form a straight line of four segments. I also think an ASCII representation doesn't necessarily need to be parsed at all: I think it can be solved straight via manipulation of the character grid (in fact, this should be doable in Retina). \$\endgroup\$ Commented Dec 21, 2015 at 9:45
  • 1
    \$\begingroup\$ 1. It would be clearer to talk about drawing a straight line segment through 4 marked and one unmarked lattice point, as "straight line" often implies that it's infinite. 2. It seems that the lines must be axis-aligned or at 45 degrees to the axis. If so, it would be good to state that explicitly in the description of play. 3. The page linked in the first sentence is very uninformative. I assume you did it because the diagrams on the Wikipedia page are for a different initial setup, but there must be some better external link. \$\endgroup\$ Commented Dec 21, 2015 at 9:48
  • \$\begingroup\$ In that case I would go for the ASCII art representation. It also depends to some extent on which is the most convenient way for you to obtain / generate test cases. \$\endgroup\$ Commented Dec 21, 2015 at 9:51
  • \$\begingroup\$ @PeterTaylor Thanks, I'll edit those suggestion in. As for the page I linked, did you see the navigation in the left iframe? (I overlooked that at first.) I'll link to Wikipedia as well though. \$\endgroup\$ Commented Dec 21, 2015 at 9:52
  • \$\begingroup\$ I agree with Peter that the website is a bit of a mess. There are many variations of the game, so I think you should state that this is the 5T variant (identified by the fact that Christopher Rosin holds the records for 5T at 178 moves and 5D at 82 moves.) It took me a while to work out why Marc Bertin at 216 moves in 1974 was not the record holder: (He was playing 5T+.) Only the 5T (endpoints of parallel lines touching allowed) and 5D (endpoints of parallel lines must be disjoint) variants are unsolved according to the website. \$\endgroup\$ Commented Dec 21, 2015 at 9:57
  • \$\begingroup\$ The person who wrote that site needs to be dragged kicking and screaming into the 21st century. But I'd prefer a link to morpionsolitaire.com/English/Rules.htm and the navigation be damned than a link to the front page. \$\endgroup\$ Commented Dec 21, 2015 at 10:01
5
\$\begingroup\$

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.

enter image description here


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]
\$\endgroup\$
1
  • \$\begingroup\$ You should specify the hashing function, if you don't want the hashing function is a mod 32 or worse, return 4. \$\endgroup\$
    – Xwtek
    Commented Jan 14, 2016 at 14:34
5
\$\begingroup\$

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)

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

\$\endgroup\$
7
  • \$\begingroup\$ For the third test case, can't you get a four-side polygon (-5,5) -- (5,5) -- (1,0) -- (-1,0) -- (-5,5)? (or (0,-5) -- (-1,0) -- (0,1) -- (1,0) -- (0,-5)) \$\endgroup\$
    – David
    Commented Feb 16, 2016 at 0:09
  • \$\begingroup\$ @David Thanks for catching that. I will fix it tomorrow, \$\endgroup\$
    – Arcturus
    Commented Feb 16, 2016 at 5:06
  • \$\begingroup\$ This could probably use some more test cases where the result is not the convex hull... if possible even one where none of the points of the convex hull are part of the solution. \$\endgroup\$ Commented Feb 16, 2016 at 7:45
  • \$\begingroup\$ @MartinBüttner The last test case is not the convex hull, as (10,0) and (10,10) are not included in the output polygon. \$\endgroup\$ Commented Feb 16, 2016 at 15:08
  • \$\begingroup\$ @TimmyD The emphasis in my sentence was on "more". ;) (I admit that may not have been obvious.) \$\endgroup\$ Commented Feb 16, 2016 at 15:09
  • \$\begingroup\$ @MartinBüttner I read it as "This could probably use some more test cases, [such as] where the result is not the convex hull" ... yay, English. \$\endgroup\$ Commented Feb 16, 2016 at 15:15
  • \$\begingroup\$ @TimmyD I like ambiguity more than most people. \$\endgroup\$ Commented Feb 16, 2016 at 15:22
5
\$\begingroup\$

Battle Snake

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.
\$\endgroup\$
5
\$\begingroup\$

Count the Cats

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]

\$\endgroup\$
15
  • 2
    \$\begingroup\$ I feel like this is probably a dupe of either the goat question or the rice question. I'm not sure that it being a test battery question or the precise subimage to identify really makes it much different from these other ones? \$\endgroup\$ Commented Jun 23, 2016 at 19:17
  • 2
    \$\begingroup\$ @FryAmTheEggman I don't think it's a dupe of goats - goats wanted a boolean classification, where this one asks for a count. The rice question is closer, but there is a possibility (and perhaps a need) for different approaches, given that a) cats can overlap, b) cats come in different colors, and c) cats have much more complex shapes than rice grains (which are ellipses). \$\endgroup\$
    – user45941
    Commented Jun 23, 2016 at 19:19
  • \$\begingroup\$ "Submissions must output and terminate within 10 seconds for a single image." I don't know about that, counting the amount of cats and only cats is a rather difficult task already, a 10-second limit seems really small. Perhaps a couple minutes? \$\endgroup\$
    – Downgoat
    Commented Jun 23, 2016 at 20:03
  • \$\begingroup\$ Also, I think there should be some specification for how the cats would appear. At least having the full cat's face showing would make this challenge more approachable. If a test-case shows the back of a cat that seems a bit too difficult for a PPCG challenge. Also: Will there be a mix of cats and other animals? Are built-ins allowed (I'm very sure there's mathematica builtin)? \$\endgroup\$
    – Downgoat
    Commented Jun 23, 2016 at 20:07
  • 1
    \$\begingroup\$ @Upgoat The time requirement can be extended. The number of cats will always be clear to a human viewer with 20/20 eyesight and adequate attention for detail. The challenge is about counting cats, not about picking out camouflaged cats, so there won't be any excessive trickery in the test images. Built-ins are allowed, but I'm on the fence about whether or not I'm going to allow them to be competitive, since Mathematica is likely the only language that would benefit from built-ins. \$\endgroup\$
    – user45941
    Commented Jun 23, 2016 at 20:12
  • 1
    \$\begingroup\$ Showing a picture of a dog and expecting a zero output doesn't seem fair. Writing a program that distinguishes between dogs and cats seems like a difficult enough task as it is, and you have it here as sort of an afterthought. Empty images should be emptier, imo. \$\endgroup\$
    – Liam
    Commented Jun 25, 2016 at 22:45
  • 1
    \$\begingroup\$ @Liam On the other hand, if all of the test images consisted of 0-5 cats and no other animals, it would be too easy to get a perfect score. Having harder test cases means that submissions will have room for improvement, and thus there will be more competition. \$\endgroup\$
    – user45941
    Commented Jun 27, 2016 at 1:46
  • \$\begingroup\$ Is fitting allowed? I think learning will probably be the most practical approach to this challenge. Though this does need some specification before it's ready to post imo and limits on the possible inputs as I doubt any answer will be able to conform to the wide variety of things cats can be e.g. color, position, shape, size, direction, camera position, etc. \$\endgroup\$
    – Downgoat
    Commented Jun 27, 2016 at 5:15
  • 1
    \$\begingroup\$ @Downgoat As per usual with these types of challenges, optimizing for the test cases is not allowed. However, given that a ML-oriented approach would be interesting and perform well on this challenge, I'd be willing to include a training set, separate from the scoring set. As for limits on possible inputs, I'm trying to work out a good set. \$\endgroup\$
    – user45941
    Commented Jun 27, 2016 at 5:41
  • 2
    \$\begingroup\$ I think the part about the dog makes this a chameleon challenge -- distinguishing a cat from a dog is much harder than identifying and counting cats on an image free of distracters. \$\endgroup\$
    – xnor
    Commented Jun 27, 2016 at 23:48
  • \$\begingroup\$ @xnor On the other hand, without the distracters, it would likely be too easy to get a perfect score. \$\endgroup\$
    – user45941
    Commented Jun 28, 2016 at 2:48
  • \$\begingroup\$ Distinguishing a cat from a dog on a picture already requires decently advanced algorithms (CNNs are the first that come to mind) which in turn require a LOT of training data to generalize decently. \$\endgroup\$
    – Fatalize
    Commented Jun 29, 2016 at 9:09
  • \$\begingroup\$ @Fatalize Would using non-mammilian animals (such as lizards and birds) be better in your opinion? \$\endgroup\$
    – user45941
    Commented Jun 29, 2016 at 9:10
  • 1
    \$\begingroup\$ @Mego It probably would be easier because it wouldn't force people to use machine learning techniques (You could use texture comparison to distinguish feathers from scales, color detection, etc.). Counting the number of each is an added difficulty that makes it maybe too difficult as a whole. Only classifying is easier but probably a dupe of the goats challenge. Only counting might be good though. \$\endgroup\$
    – Fatalize
    Commented Jun 29, 2016 at 9:14
  • \$\begingroup\$ The problem with this scoring technique is that even if people make legit attempts at counting the cats, they will try to optimize their code for the limited test set, which will make their approaches less general on new data. One solution could be to provide a validation set (for say 2 weeks if that's the time frame in which you can post an answer) on which people can evaluate their answers, and choose the winning answer based on a test set that was not available during those 2 weeks containing new images. \$\endgroup\$
    – Fatalize
    Commented Jul 1, 2016 at 13:27
5
\$\begingroup\$

The Ifelse Tower

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 , so shortest answer in bytes gets the job -err wins

\$\endgroup\$
3
  • 5
    \$\begingroup\$ I'd allow a single optional trailing linefeed. A lot of languages print full lines by default. In some it's annoying to suppress that and in some it's impossible. \$\endgroup\$ Commented Jul 20, 2016 at 7:30
  • 1
    \$\begingroup\$ Why enforced an output to stdout? \$\endgroup\$
    – aloisdg
    Commented Jul 20, 2016 at 12:41
  • \$\begingroup\$ This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 14 days if you have any objections and would still like to finish and post this challenge yourself. \$\endgroup\$ Commented Jun 4, 2017 at 13:05
5
\$\begingroup\$

Interpret a Formal Grammar

Given a context-free grammar, and a string, parse the string using the formal grammar and output the matches for the non-terminals.

Examples

First line is string, following lines are grammar, then is the main grammar to parse, last line is output.

123

n -> any of
     0 1 2 3 4 5 6 7 8 9
N -> n N
     n

N

N [ n [1], n [2], n [3] ]
2+2*(4/2)

o -> any of
     + - / *
n -> any of
     0 1 2 3 4 5 6 7 8 9
E -> o E E'
     ( E ) E'
     n E'
E' -> o E E'
     o E'
     ε

E

E [ n [2], E' [ o [+], E [ n [2], E' [ε]  ] ] ]
a b

S -> S' S
     ε
S' -> a   b

S

S [ S' [a], S' [ ], S' [b] ]

This grammar is the same as regex: [a b]+

Spec

Details:

  • All recursion will be right-recursive
  • Rule names will consist of A-Z a-z α β γ Γ and may have a ' at the end.
    • Valid Rule names:
      • A
      • Γ
      • AB
      • αβ
      • foo'
      • faαβdg'
    • Invalid Rule names:
      • 'ab (' will be at the end)
      • ab'' (two ''s)
      • code golf (spaces not allowed in rule names)
  • Nonterminals will be lowercase, terminals upercase
  • A derivation format will be:

    <rule name> -> <rule>
                   <rule>
                   <rule, etc.>
    

    meaning the rules will be lined up (when in a monospace font), by spaces.

  • Symbols/rule-names will never be repeated
  • ε (epsilon) means empty. i.e. ""

Rule definition:

  • If the initial rule is "any of", the second rule will exist and will be a space separated list of symbols/rule-names (maybe more than one char). There will be no rules after this
  • Else, the rule will consist of space-seperated tokens which either refer to a rule or a literal. If it is not a valid rule name, assume it is a literal which should be treated as if it is a terminal.

Summing up, for input you will be given the string to parse, the grammar, and the rule to parse.

Output:

You may output in whichever format you like as long as it is able to convey the following information. You must somehow label the match to their respective rule names. You may optionally not label terminals.

Challenge Rules:

  • Feel free to assume the input can always be parsed by the given grammar.
  • External libraries (ones that have to be imported), are not allowed
  • If your language has built-in parsing tools (e.g. regex) those are allowed
  • If your language has a built-in to parse a grammar (i.e. some formal grammar parser), these are allowed but your solution is non-competing and you must clearly state this in the header of your answer.

This is so shortest code in bytes wins!

I may award a bounty to any particularly ingenious solutions, so try to add an explanation!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 1. Why the special-case Greek letters in the valid rule names? That seems to add complication for no benefit. 2. Am I correct in thinking that the only way to match a literal space character is as part of an "any of" rule? Some test cases involving literal spaces would be useful. 3. What does "Symbols will never be repeated" mean? 4. The spec for the rule definition uses the words "symbols" and "tokens". It's not clear to me whether these are synonyms, and if not then what the distinction is. 5. May we assume that there is a valid parse tree for the given input? \$\endgroup\$ Commented Jun 11, 2016 at 11:47
  • \$\begingroup\$ @PeterTaylor greek letters are often used in grammars. I'll address number 2, and 4. Symbols are a name of a derivation(s). \$\endgroup\$
    – Downgoat
    Commented Aug 7, 2016 at 22:22
  • \$\begingroup\$ Trying to outsource compiler design for cheddar? Lol, jk, +1! \$\endgroup\$ Commented Aug 7, 2016 at 23:29
  • 1
    \$\begingroup\$ I must say that I never saw any Greek letters except for episilon in the formal language and parsing courses I took, but that wasn't really my point. My point was the special-casing of three lower-case and one upper-case Greek letters. If rule names could contain any character other than - > then it would be simpler. If they could contain any Unicode alphabetic character then it would be simpler (at least for regex users). Also, 6. "Nonterminals will be lowercase, terminals upercase" Does this mean that mixed case tokens are always literals? \$\endgroup\$ Commented Aug 8, 2016 at 7:30
5
\$\begingroup\$

Esolang Interpreters

Using a programming language from this version of this list, write an interpreter for the next language on the list. For example, if you choose to start with LOCK, you would write an interpreter for LOLCODE. Continue this pattern (use LOLCODE to write an LCBF iterpreter, etc)
If specs of a language are unclear and the compiler is nonexistant or closed-source, ask me and I'll decide whether or not to take it off the list.

Wining Criteria:
The longest streak of compilers wins.


Proposed Edits:
Make several defined starting points. (this would make many answers too similar, though)


Edits: changed from list of all esolangs to just turing complete ones.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ I like it, but it may be a trivial task depending on what language you choose \$\endgroup\$ Commented Aug 24, 2016 at 21:37
  • \$\begingroup\$ I think this would be better as a similar challenge to the enterprise quality code, but where the winner is the one who does the most languages at the end at you need to go in order. If you don't think so, I'll make a separate sandbox post. \$\endgroup\$
    – Riker
    Commented Aug 24, 2016 at 21:39
  • 1
    \$\begingroup\$ In order to prevent edits, you can simply use the version in the url: esolangs.org/w/index.php?title=Language_list&oldid=49177 \$\endgroup\$ Commented Aug 24, 2016 at 21:41
  • 1
    \$\begingroup\$ I agree with Easterly, but I'd also make it a cycle based-system. Aka, the interpreter for "!!!Batch" must be written before the interpreter for "???" can be written. You could also have multiple starting points, one for each letter. \$\endgroup\$ Commented Aug 24, 2016 at 21:45
  • \$\begingroup\$ Actually, better idea, score them based on the number of consecutive interpreters they write. \$\endgroup\$ Commented Aug 24, 2016 at 21:48
  • \$\begingroup\$ How will you deal with cases where one language is a joke language and/or not Turing complete, and therefore cannot interpret the next language? \$\endgroup\$ Commented Aug 24, 2016 at 21:56
  • \$\begingroup\$ @El'endiaStarman should I use this list instead? \$\endgroup\$ Commented Aug 25, 2016 at 0:09
  • \$\begingroup\$ @Nathan Merrill I think I will do that, yes. Great suggestions. \$\endgroup\$ Commented Aug 25, 2016 at 0:10
  • \$\begingroup\$ @BaldBantha: That would be better, but you may still run into problems such as languages being technically Turing complete, but entirely impractical. For instance, try multiplying two numbers in Pancake Stack. \$\endgroup\$ Commented Aug 25, 2016 at 0:12
  • \$\begingroup\$ @El'endiaStarman Oh, well this challenge isn't supposed to be easy. I assume the first few answers will include 2-3 interpreters (depends on the starting points, TBH), but I think it would stall for a while. TLDR: I don't feel like classifying several hundred langueges as practical or not. \$\endgroup\$ Commented Aug 25, 2016 at 0:16
  • \$\begingroup\$ The bigger issue I see is that many languages don't have completely solid specs, so it's not clear what counts as a valid interpreter of the language. \$\endgroup\$ Commented Aug 25, 2016 at 8:53
5
\$\begingroup\$

Sesquiprimes

Given a non-negative integer N, output the Nth sesquiprime integer.

We say that a positive integer I is sesquiprime if I + ⌊I/2⌋ is prime (where ⌊...⌋ is the floor function).

For example, 25 is a sesquiprime because 25 + ⌊25/2⌋ = 25 + 12 = 37, which is prime.

Sequence A158708 is the sequence of prime sesquiprimes.

Inputs and outputs

  • N may be 0-indexed or 1-indexed, please indicate which of the two your solution uses.

  • Inputs and outputs must be in the decimal base.

  • N may be taken through STDIN, as a function argument, or anything similar.

  • The output may be printed to STDOUT, returned from a function, or anything similar.

Test cases

The following test cases are 0-indexed.

N        Output

0        2
1        5
2        9
4        21
8        45
15       93
16       101
23       149
42       305
100      853
1000     11693

Scoring

This is , so the shortest answer in bytes wins.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ I don't think the link to prime sesquiprimes adds anything other than a possibility for mistakes by people too lazy to read specs fully (like me) \$\endgroup\$ Commented Sep 4, 2016 at 17:34
  • \$\begingroup\$ @JonathanAllan True. Would adding it as a comment be better to make it less appear like part of the challenge? \$\endgroup\$
    – Fatalize
    Commented Sep 4, 2016 at 17:40
  • 1
    \$\begingroup\$ Including the link as a comment and/or prefixed by Related: would probably be clearer. \$\endgroup\$
    – Dennis
    Commented Sep 4, 2016 at 18:11
  • \$\begingroup\$ This seems close to finding primes that are 1 mod 3. \$\endgroup\$
    – xnor
    Commented Sep 5, 2016 at 10:18
5
\$\begingroup\$

Slay

This KoTH is based off of the computer game, Slay. Try it out, its way fun.

TLDR

  • You start off with a bunch of small territories: you try to merge them and capture as much land as possible.
  • Each territory has its own economy: each hex gives you 1 gold per turn.
  • Warriors can capture and protect territory, but cost money to maintain.
  • If you run out of money, all units on that territory die

Map

  • A hexagonal map is generated using Perlin noise.
  • Each hexagon is randomly assigned to a player. Players will start with a similar number of hexagons, as well as a similar number of territories (see below)
  • Hexagons that touch the edge of the map (or a hole in the middle), are on the beach
  • Each tile has a 1/5 chance of starting with a tree: Palm tree if on the beach, pine tree otherwise
  • Hexagons may contain a warrior, house, tower, grave, or palm/pine tree

Territory

  • A block of 2 or more hexagons with the same owner is considered a territory
  • All territories contain exactly 1 house.
    • If a territory ever doesn't have a house, it gets one in a random location, preferring: empty hexes, trees, graves, towers, and then warriors. (in that order)
  • A territory "death" occurs when it is reduced/split into a single hexagon.
    • Houses turn into a pine/palm (if on the beach) tree
    • Warriors die (turn into graves) at the start of their next turn
    • Towers disappear
  • If two territories grow so that they touch, they merge and the smaller territory's house disappears.

Finanaces

  • Each territory has its own reserve/income
  • Each territory starts with 10 gold in its reserve
  • Territories generate 1 income at the end of each turn for each tree-less hexagon
  • If you don't have enough money to pay for your units at the end of your turn, then all of your units in that territory will die (turn into graves) at the start of your next turn.
  • If a territory splits, then the larger of the two gets all of the reserve.
  • If a territory combines, their reserves combine

Defense

  • Certain objects give defense to its hexagon and all adjacent friendly hexagons:
    • Houses (1): cannot be built, but every territory has exactly one
    • Towers (2): can be built for 15 gold
    • Warriors (strength): see below

Map objects

Warriors

  • A warrior has a strength between 1 to 4 (inclusive)
  • A warrior costs 10*strength to build
  • A warrior costs 2*3^(strength-1) gold each turn. This means that a 4-str warrior costs you a whopping 54 gold per turn
  • A warrior can move a maximum of 4 hexes each turn. Moving through enemy lands is not allowed. Capturing enemy lands ends the warrior's turn.
  • If you move/build a warrior onto a friendly warrior, they combine, and their strength is summed.
    • Trying to make a warrior of strength > 4 doesn't work
    • If the friendly warrior hadn't moved yet, the new unit can still move
  • A warrior can capture an adjacent hexagon if its defense rating is lower than its strength

Trees

  • Trees prevent a hexagon from generating income
  • Trees grow at the end of each round:
    • Palm trees grow onto all unoccupied adjacent beach tiles
    • Any unoccupied tile that is adjacent to two pine trees grows another pine
  • Trees can be removed by moving a unit onto them
  • Graves turn into a pine/palm (if on beach) tree at the end of the round

Game flow

  • Between 2 to 6 players can play on a single map. (The size of the map depends on the number of players. You can expect about 50 hexagons per player)
  • Turn order is randomized, but is consistent within a single game
  • Once a player owns all hexagons, they win!
\$\endgroup\$
2
  • \$\begingroup\$ @zyabin101 still not ready yet. \$\endgroup\$ Commented Aug 31, 2016 at 21:35
  • 1
    \$\begingroup\$ @zyabin101 + others finished my post! It took me a bit to ensure I got all corner cases correct. \$\endgroup\$ Commented Sep 6, 2016 at 15:41
1
3 4
5
6 7
157

You must log in to answer this question.

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