493
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| |
\$\endgroup\$

2997 Answers 2997

1
18 19
20
21 22
100
2
\$\begingroup\$

Deep-dichotomize a list

Given a list, dichotomize it (i.e. split it in half), then dichotomize both resulting sublists, etc., until you reach sublists of length 1.

For example, given [1,2,3,4,5,6,7,8]:

  Dichotomize: [[1,2,3,4],[5,6,7,8]]
  Map dichotomize: [[[1,2],[3,4]],[[5,6],[7,8]]]
  Map map dichotomize: [[[[1],[2]],[[3],[4]]],[[[5],[6]],[[7],[8]]]]
  We end here because we only have singletons

If the list has an odd length, the longest of the two lists should be the second one. For example, [1,2,3,4,5] is dichotomized into [[1,2],[3,4,5]].

The content of the list is irrelevant (you can use whatever you want). You can use any list-like representation of your language, as long as both the Input and the Output use the same representation.

Test cases

Input                          Output
[1]                            [1]
[1,2]                          [[1],[2]]
[1,2,3,4]                      [[[1],[2]],[[3],[4]]]
[1,2,3,4,5,6,7,8,9]            [[[[1],[2]],[[3],[4]]],[[[5],[6]],[[7],[[8],[9]]]]

Scoring

This is , so the shortest answer in bytes wins.

| |
\$\endgroup\$
  • \$\begingroup\$ Does the output have to be a list/array? It seems that you're really building a binary tree, and being more flexible in the output would allow languages like Haskell with strict typing which doesn't allow lists of varying depth to participate. \$\endgroup\$ – Peter Taylor Jun 28 '17 at 10:19
  • \$\begingroup\$ @PeterTaylor To me, You can use any list-like representation of your language includes nested lists and so trees. Maybe I should be clearer. \$\endgroup\$ – Fatalize Jun 28 '17 at 10:22
  • \$\begingroup\$ I don't think a binary tree is really list-like. \$\endgroup\$ – Peter Taylor Jun 28 '17 at 10:23
  • \$\begingroup\$ Suggested tags: code-golf, array-manipulation, recursion. \$\endgroup\$ – Erik the Outgolfer Jun 28 '17 at 13:25
  • 1
    \$\begingroup\$ Third testcase is a bit off, a ] is missing at the end. \$\endgroup\$ – Erik the Outgolfer Jun 30 '17 at 12:58
  • \$\begingroup\$ "If the list has an odd length, the longest of the two lists should be the second one" seems like unnecessary fluff to me. \$\endgroup\$ – scatter Jun 30 '17 at 14:42
  • \$\begingroup\$ @Christian Why? \$\endgroup\$ – Fatalize Jun 30 '17 at 14:48
  • \$\begingroup\$ @Christian No it's not, how should I split [1, 2, 3, 4, 5] without that information? \$\endgroup\$ – Erik the Outgolfer Jun 30 '17 at 15:16
  • 1
    \$\begingroup\$ @Fatalize Because you could just as easily say it doesn't matter, whichever your language does by default is fine. \$\endgroup\$ – scatter Jun 30 '17 at 15:52
  • \$\begingroup\$ I also think it would be cleaner to allow odd splits to go whatever way. \$\endgroup\$ – xnor Jul 7 '17 at 5:07
2
\$\begingroup\$

Create a "Neverending" Quine

Your task is to create a program which, when run, outputs its source code repeatedly until stopped. You are allowed to have an extra newline between outputs.
NOTE: All standard loopholes are strictly forbidden. That means cheating quines, etc.


This is , so may the shortest answer win and the best programmer prosper...

| |
\$\endgroup\$
  • \$\begingroup\$ Never mind. Found a duplicate. \$\endgroup\$ – ckjbgames Jun 30 '17 at 23:32
  • \$\begingroup\$ Please delete this proposal then and edit it down to a stub. Thanks! \$\endgroup\$ – HyperNeutrino Jul 25 '17 at 0:26
2
\$\begingroup\$

It halts. But why?

Cops/Robbers section

The robbers/cops section can be found here.


Challenge

Cops

Your job is to write a program that always halts. It can do anything it likes, as long as, given any input, it eventually stops. You must also write a mathematical proof that it stops. Two weeks after you have posted your answer (since math is hard, we want to give the Robbers a chance to steal your academic success), you should edit in this mathematical proof. Once you have done so, you are safe, and your score will be the length of your program (in bytes). Whichever safe program has the lowest score wins!

Robbers

Your job is to write a mathematical proof that a given cops program halts, and post it as an answer. You must do so before the cop posts their proof.

You get 1 point for each post cracked, unless you crack it within 24 hours, in which case it is only 0.1 points (this is to prevent people from racking up points on easy answers). You obviously cannot crack your own submissions.

Notes

  1. Cops may not use undocumented or incorrectly documented features of the programming language they are using.
  2. Although the proofs will be written in the informal style common within mathematics (as opposed to completely formal proofs), they must theoretically be valid in the framework of ZFC. This will not come into play for most answers, seeing as most of mathematics can be formalized in ZFC, but some might if they use crazy metamathematical shenanigans (please do not do this (just kidding, go crazy kids)).
    • This means that cops must write programs that can be proven to halt in ZFC. This means, for example the program if isProofThatZFCisInconsistient(input) then infiniteLoop else stop) would be invalid, since although this program always halts (presumably), you cannot prove this fact in ZFC.
  3. Cops, your program is not safe until you post the proof.
| |
\$\endgroup\$
  • 3
    \$\begingroup\$ This seems to be more a knowledge of obscure theorems contest than a programming contest. While the Curry-Howard correspondence says that the two are related, IMO this isn't really on topic. \$\endgroup\$ – Peter Taylor Jul 6 '17 at 13:30
  • \$\begingroup\$ @Peter Taylor well, you would also need to golf the obscure theorems. \$\endgroup\$ – PyRulez Jul 6 '17 at 14:09
  • \$\begingroup\$ ^ and obfuscation could come into play. \$\endgroup\$ – FlipTack Jan 3 '18 at 19:22
2
\$\begingroup\$

ASCII Art Turtle

As you know, the LOGO programming language allows you to manoeuvre a turtle and draw lines in a graphical way. It occurs to me that we can do this for .

A minimal set of commands to produce would be the R(otate right), F(orward) and P(en) commands. For example, the string FPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPF would produce the following output:

\|/
- -
/|\

However that AAT code is rather inconvenient so I have chosen the following slightly more compact instruction set:

  • F Move one cell in the current direction. Initially the current direction is east. If the pen is down, the cell just vacated is set to one of -/|\ appropriately.
  • B Move one cell in the reverse direction. (Initially this would be west, of course.) The cell vacated is set in the same way as for F (since the output characters are all symmetric).
  • R Rotate right 45°. Only the current direction changes; nothing is drawn and the current position does not move.
  • L Rotate left 45°. Otherwise as per R.
  • D Lower the pen. Note that the pen starts lowered.
  • U Raise the pen.

The above image could therefore be drawn using the command string BULFDBULFDBULFDBULFDBULFDBULFDBULFDB, while the string LFFUBRFDFFFFFFFFFFFFFFFFFRFFRFBRRFFFFFFFFFFFFFFFFFFFFFUBLLFDFFBLLFFFFFFFFFFFFFFFFFFFFFUBRRFDFRRFFFFFFFFFFFFFFFFFFFFFURBDBBUFLBDBBBBBBBBBLLFFFURBDBBBUFRBDBBBLBB should hopefully produce this somewhat familiar picture:

 /-----------------\ 
/                   \
---------------------
|                   |
---------------------
|                   |
---------------------
\                   /
 \---------|  /----/ 
           | /       
           |/        

Your function or program must take input as a string, or whatever the nearest equivalent is in your language, and output a newline-delimited or newline-terminated string. (For those of you used to using TIO it should be possible to paste the raw string into the ▼ Input field and show the output directly in the ▼ Output field.) Extra blank rows or columns are not allowed, but you are allowed to pad all the lines to the length of the longest non-blank line. You can take input in lower or mixed case if you prefer. You can assume that the input will only use those six letters. You can further assume that U and D commands alternate. You can also assume that you will never write in the same place twice.

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

| |
\$\endgroup\$
2
\$\begingroup\$

An order of primeness

Introduction

In a recent question the concepts of super-primes were explored. A super-prime is a prime whose index is also a prime.

  • 2 is not a super-prime, its index is 1
  • 3 is a super-prime, its index is 2
  • 5 is a super-prime, its index is 3
  • 7 is not a super-prime, its index is 4
  • ...

The first few of these super-primes are 3, 5, 11, 17, 31, 41, 59, ...

Let us call these primes of at least order 2, because they are more prime than regular primes (which are only of order 1).

Primes of order of 3 or greater can be defined similar. A prime is of order 3 if its index is a prime of order 2.

The first few of the primes at least of order 3 are 5, 11, 31, 41, 59, 127, 179, 277, ...

This is sequence A049076. It was defined by Neil Fernandez in 1999. More information can be found in his Exploring Primeness Project.

Task

Given a prime, return its order.
More formally

  • INPUT: A single integer which is guaranteed to be a prime
  • OUTPUT: A single integer which is the order of the input.
  • You can either return or print the result.

This is , so shortest code wins.

Testcases

           2 ->  1
           3 ->  2
           5 ->  3
           7 ->  1
       52711 ->  9
435748987787 -> 11 (happens to be the 11. Prime of order 11)

Sandbox Questions

  1. Does it need any more clarification?
  2. Should I define order 0 (not a prime) and allow any number as input, or would that over-complicate the challenge?
  3. Primes of higher order tend to get big very fast. Should I somehow specify that a language only has to work for test-cases it can actually handle or is their a consensus already?
  4. Is the introduction too big?
| |
\$\endgroup\$
  • \$\begingroup\$ This is just a loop round the linked question, and as such qualifies as a duplicate for the purposes of this site. \$\endgroup\$ – Peter Taylor Jul 10 '17 at 14:04
  • 1
    \$\begingroup\$ I think this might be an interesting question. \$\endgroup\$ – CalculatorFeline Jul 10 '17 at 22:14
  • \$\begingroup\$ Last test case -> 10 (or all the other cases ->+1) \$\endgroup\$ – J42161217 Jul 10 '17 at 23:24
2
\$\begingroup\$

These are two separate challenges.


Convert to mixed-radix ZYX…432.234…XYZ

Related: Convert from mixed-radix ZYX…432.234…XYZ and Convert to and from the factorial number system.

Given a non-negative real number (no greater than 1×1040 or the biggest your language can comfortably accommodate, whichever is less) convert it to mixed-radix ZYX…432.234…XYZ using the base-36 digits [0-9A-Z] or [0-9a-z] with no leading zeros (except for values smaller than 1). Any reasonable rounding is fine.

Examples

00 (0 × !1)
11 (1 × !1)
210 (1 × !2 + 0 × !1)
311 (1 × !2 + 1 × !1)
420 (2 × !2 + 0 × !1)
421300 (1 × !4 + 3 × !3 + 0 × !2 + 0 ×!1)
1004020 (4 × !4 + 0 × !3 + 2 × !2 + 0 ×!1)
123452304111
42949672958B6570020211
1000000000017A5726651220
184467440737095516157BC43F35350835000211
0.50.1
0.3333333333333333330.02
0.250.112
0.10.0022
5.12521.003
2.7182818284590452351.111111111111111111
0.0013888888888888890.00001


Convert from mixed-radix ZYX…432.234…XYZ

Related: Convert to mixed-radix ZYX…432.234…XYZ and Convert to and from the factorial number system.

Given a string (no longer than 71 characters or the maximum that gives a result your language can comfortably accommodate, whichever is less) convert it from mixed-base mixed-radix ZYX…432.234…XYZ using the base-36 digits [0-9A-Z] or [0-9a-z]. Any reasonable rounding is fine.

Examples

0 (0 × !1) → 0
1 (1 × !1) → 1
10 (1 × !2 + 0 × !1) → 2
11 (1 × !2 + 1 × !1) → 3
20 (2 × !2 + 0 × !1) → 4
1300 (1 × !4 + 3 × !3 + 0 × !2 + 0 ×!1) → 42
4020 (4 × !4 + 0 × !3 + 2 × !2 + 0 ×!1) → 100
230411112345
8B65700202114294967295
17A572665122010000000000
7BC43F3535083500021118446744073709551615
0.10.5
0.020.333333333333333333
0.1120.25
0.00220.1
21.0035.125
1.1111111111111111112.718281828459045235
0.000010.001388888888888889


| |
\$\endgroup\$
  • \$\begingroup\$ I think this is ready. \$\endgroup\$ – Zacharý Jul 11 '17 at 21:56
  • \$\begingroup\$ I'd like this more with a list of digits 0-35 in the factorial base rather than including letters. \$\endgroup\$ – xnor Jul 13 '17 at 8:16
  • \$\begingroup\$ @xnor Interesting. In that case, there should be no specific upper limit, right? \$\endgroup\$ – Adám Jul 13 '17 at 8:17
  • \$\begingroup\$ @Adám That's right, unless you want a limit for the sake of languages' number bounds. \$\endgroup\$ – xnor Jul 13 '17 at 8:18
  • \$\begingroup\$ @xnor I assume that's covered by default rules. This simplifies the challenge text, so I'll make the change. Thanks \$\endgroup\$ – Adám Jul 13 '17 at 8:18
  • \$\begingroup\$ @xnor How is this? \$\endgroup\$ – Adám Jul 13 '17 at 8:24
  • \$\begingroup\$ @Adám Looks good to me. Is your plan to post a challenge for just one direction? \$\endgroup\$ – xnor Jul 13 '17 at 8:32
  • \$\begingroup\$ @xnor Uh, did you read the post? \$\endgroup\$ – Adám Jul 13 '17 at 8:33
  • \$\begingroup\$ @Adám Yes, and I'm not sure if your plan is to post two challenges, or just whichever direction is more interesting. \$\endgroup\$ – xnor Jul 13 '17 at 8:51
  • \$\begingroup\$ @xnor Two challenges. However, I just noticed that factoradic can easily represent floats too, so should I extend/modify the challenges to that? It would certainly make them different from the existing one. \$\endgroup\$ – Adám Jul 13 '17 at 8:53
  • \$\begingroup\$ Yes, you should do that so built-ins won't be useful (cough Jelly cough) in addition to distinguishing this from the existing challenge. \$\endgroup\$ – Zacharý Jul 13 '17 at 19:57
  • 1
    \$\begingroup\$ The original challenge with letters was way better... \$\endgroup\$ – J42161217 Jul 14 '17 at 6:25
  • \$\begingroup\$ I actually agree with @Jenny_mathy because languages like Jelly naturally output different bases in a list format, rather than a string of letters. \$\endgroup\$ – Zacharý Jul 14 '17 at 13:17
  • \$\begingroup\$ @Jenny_mathy Like this? \$\endgroup\$ – Adám Jul 14 '17 at 14:22
  • \$\begingroup\$ @Zacharý Ping ^ \$\endgroup\$ – Adám Jul 14 '17 at 14:22
2
\$\begingroup\$

Solve the Trolley Problem

Philosophers have long pondered the Trolley problem. Unfortunately, this no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us!

Your program will take as input a (finite) directed graph (with at most one edge from x to y, for any x and y), with a designated node, and a nonnegative integer attached to each edge (representing the number of people tied to that track). In addition, every node has at least one exit edge.

The trolley starts at the designated node. Each turn, if the trolley is at node x, the utilitarian selects an edge (x,y). The people on that edge die, and trolley is now at edge y. This process continues forever.

Note that people can only die once, so if the edge (x,y) has n people tied to it, and the trolley runs over them, say, 100 times, it will still only result in n deaths.

The utilitarian makes his choices in such a way as to minimize the number of people that die (which is guaranteed to be finite, since there are only finite people). Your program will output this number.

You may take the input graph in any reasonable way you like. For example, you could take it as a matrix, and count the designated node as the one labeled 0. Or you could use something like x1,y1,n1;x2,y2,n2;.... For example 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 to represent the standard trolley problem (with loops at the end).

Testcases:

  • 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (Go from 0 to a, a to c (killing one person), and then keep looping the trolley from c to c).
  • 0,0,1;0,a,5;a,a,0 -> 1 (Keep going from 0 to 0, running over 1 person for all eternity),
  • 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (note that the greedy solution of going to b would be incorrect))
  • 0,a,1;0,b,5;a,b,1;b,a,1 -> 3 (0 -> a -> b -> a -> b -> ...)
  • 0,a,1;0,b,1;a,a,0;b,b,0 -> 1 (Note that there are two different options that the utilitarian might take that both kill only one person)

This is , so the shortest answer wins! Good luck.

Notes: There will be no sick loop de loops and multitrack drifting is banned.

| |
\$\endgroup\$
  • \$\begingroup\$ So basically: find the cycle of lowest weight? That's pretty similar to finding the cycle of greatest weight, which is equivalent (for integer weights) to codegolf.stackexchange.com/q/107274/194 \$\endgroup\$ – Peter Taylor Jul 22 '17 at 9:36
  • \$\begingroup\$ @Peter Taylor no, since you may have to kill lots of people to get to that cycle, or it might not be reachable at all. \$\endgroup\$ – PyRulez Jul 22 '17 at 12:26
  • \$\begingroup\$ Aha, so it's finding a rho of lowest weight. Still potentially quite similar in implementation, but certainly admits alternative approaches. It might improve clarity to explicitly describe the rho form of the paths to consider. \$\endgroup\$ – Peter Taylor Jul 22 '17 at 12:33
  • \$\begingroup\$ @Peter Taylor what is rho? \$\endgroup\$ – PyRulez Jul 22 '17 at 15:44
  • \$\begingroup\$ ρ , as in Pollard's rho which uses paths which eventually loop back on themselves to factor composite numbers. \$\endgroup\$ – Peter Taylor Jul 22 '17 at 16:08
  • \$\begingroup\$ You should delete this as it has been posted. \$\endgroup\$ – Erik the Outgolfer Jul 28 '17 at 19:41
2
\$\begingroup\$

An anagram chain

Your challenge is to create a program, P_0, that outputs P_1, that outputs P_2, that outputs... P_n, which finally outputs P_0. Every program in that chain has to be a permutation of every other program, and every program has to be distinct.

For example, if your program (P_0) was

abcd

And that generated another program (P_1)

badc

Which generated another program (P_2)

dabc

Which outputted the first program, you would have a anagram chain of length 3.

Your goal is to make as long a chain as possible, in as short a program as possible.

Your final score will be your chain length - in case there's a tie, the program with the shortest bytecount wins. If there's a tie again, the first poster wins.

Meta:

  • I need a better title. Any suggestions?
| |
\$\endgroup\$
  • \$\begingroup\$ [Related]. Actually, I'm pretty sure this is a dupe of another challenge that I can't find at the moment. \$\endgroup\$ – Shaggy Jul 23 '17 at 10:13
2
\$\begingroup\$

KotH: Atom Bomb Chess

(Draft. I'll flesh it out some more later. It will probably be implemented in JavaScript or maybe C++.)

Atom Bomb Chess is a variant of chess played much the same as regular chess. The only differences are:

  1. The game ends when one or both players have no pieces, or if 50 moves have been made without a piece being captured.
  2. When a piece is captured, all pieces a king's move away are also "captured", and the piece doing the capturing is also "captured".

For example, let's look at a 4x4:

pbbr
....
....
RBBP

Where r/R is a rook, b/B is a bishop, and p/P is a pawn. Suppose R moves forward 3 spaces. Then, it captures the p and "explodes":

..br
....
....
.BBP

The idea of this KotH is to make a program that plays Atom Bomb Chess. I will have a few programs to test your submissions against.

| |
\$\endgroup\$
  • \$\begingroup\$ This is a really cool idea! Obviously you'll need to flesh out the rules a bit more, but this is a great start. I would also suggest fixing the board size (you seem to suggest it can be played on any size board, but I think it would be easiest to set it as a constant ahead of time). \$\endgroup\$ – musicman523 Jul 23 '17 at 22:31
  • \$\begingroup\$ @musicman523 Yeah, it'd probably be played on an 8x8 \$\endgroup\$ – Conor O'Brien Jul 23 '17 at 22:35
  • 1
    \$\begingroup\$ you forgot that pawns are partially nuke proof \$\endgroup\$ – Destructible Lemon Jul 23 '17 at 23:15
  • \$\begingroup\$ @DestructibleLemon Please elaborate ? I wasn't aware there was some standard rulebook. \$\endgroup\$ – Conor O'Brien Jul 24 '17 at 1:45
  • 2
    \$\begingroup\$ I'm not entirely sure where it is, but I remember that pawns, while still being eliminated if they are capturing, or are captured, will not get removed if they are adjacent to a capture. maybe use lichess? \$\endgroup\$ – Destructible Lemon Jul 24 '17 at 2:51
  • \$\begingroup\$ @DestructibleLemon I remember playing it when I was younger with no such restriction, perhaps there are multiple variants. Why suggest lichess? Does it have that mode? \$\endgroup\$ – Conor O'Brien Jul 24 '17 at 18:02
  • \$\begingroup\$ Apart from pawns being nuke proof, the game ends as soon as you nuke the enemy king, if you play on lichess. There are videos on YouTube which include an explanation of the rules and basic "opening theory". \$\endgroup\$ – Sleafar Jul 28 '17 at 18:17
2
\$\begingroup\$

Who Won the Chess Game?

Bear with me, this is incredibly bare-bones at the moment; I'll work on this over-time, just wanted to gauge interest on the over-all idea.


Given an input list of moves l, output who won the chess game given that white always goes first, alternating moves from there. Using the following convention for naming the chess squares:

enter image description here

Where the pieces are:

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

The first assumption you will make is that the list of moves passed is a VALID chess game, to completion. The following would be an example input:

[[A2,A4],[A7,A6],...]

The first two moves given would result in:

rnbqkbnr
pppppppp
........
........
P.......
........
.PPPPPPP
RNBQKBNR

Which is white's first move, followed by black's move:

rnbqkbnr
.ppppppp
p.......
........
P.......
........
.PPPPPPP
RNBQKBNR

Then, you would continue parsing moves until a king disappears. Whichever king is left should be declared the winner.


Waiting to Gauge Interest Before Wasting Time on Full Testcase

| |
\$\endgroup\$
2
\$\begingroup\$

Nested list unpacking

In Python 3.5+, the * operator can unpack a list within a list.

[1,*[2,3,4],5] == [1,2,3,4,5]

The unpacked elements are placed directly into the outer list without increasing the list depth. Note that this is different from the nested three-element list

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

Your goal is to simplify a nested list expression by resolving all instances of unpacking. So, the output will simply be a nested list without any *.

Specifically, the input will be an expression that consists of

  • A non-empty list of expressions [..]
  • An non-empty unpacked list of expressions *[..].
  • A digit 1 through 9

The outermost layer will always be a non-empty list. The output is such an expression without any unpacking.

Input: A string of characters [],*123456789

Output: Its unpacked analogue. This can be a string or list structure.

This challenge can be done in any language. Python and other languages with the same unpacking format may not use eval or exec or equivalents.

TODO: I/O details, test cases

| |
\$\endgroup\$
  • \$\begingroup\$ This is similar to least Levenshtein distance to a balanced list (replace *[ with { and then remove unbalanced ]). \$\endgroup\$ – Peter Taylor Jul 25 '17 at 7:20
2
\$\begingroup\$

Tell me my vocabulary words! Donated.

When taking textbook notes, I need to write down the vocabulary words and their definition. So your task is to write some code that will give me the vocabulary words and their definitions!

Vocabulary words are detonated with a * on both sides of them, like this: Sentences are .-delimited, meaning that after every . a new sentence starts. An example of a valid sentence would be: This sentence has a *vocab word* in it. The vocab word in the sentence is 'vocab word'.

Input: A string of text with some words marked with asterisks. Only valid inputs will be provided, meaning that only sentences with exactly two asterisks inside of them, and there is something between the asterisks.

Output: A list or delimited string where each item is in the following format: Vocabulary word: sentence. The Vocabulary word is the vocab word found in the sentence. The sentence must be the one with the emboldened vocabulary word in it. If there is any whitespace other than the s separating the words, it needs to be stripped.

Test cases:

Input: *Alan Turing* invented the Turing machine. A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Output: *Alan Turing*: *Alan Turing* invented the Turing machine.
        *Turing machine": A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Input: What is code-golf? *Code-golf* is the best site on the SE network. But what is SE, you ask? *SE* is a group of Q&A sites, with a system to prevent bad posts.

Output: *Code-golf*: *Code-golf* is the best site on the SE network.
        *SE*: *SE* is a group of Q&A sites, with a system to prevent bad posts.

| |
\$\endgroup\$
  • \$\begingroup\$ So split on '.' and then filter to strings containing a *? Or can there be asterisks which don't mark vocabulary words? Should we trim whitespace at the start and end of the sentences? \$\endgroup\$ – Peter Taylor Apr 6 '17 at 9:54
  • \$\begingroup\$ @PeterTaylor A string surrounded by * is a vocab word, like this: *vocab word*. You need to format the outputted sentence correctly, and trim whitespace. I will edit when I have more time. \$\endgroup\$ – Comrade SparklePony Apr 6 '17 at 13:52
  • \$\begingroup\$ Are the following valid inputs or not? a) Unbalanced* asterisk; b) Empty ** vocabulary word; c) Vocabulary* word *has bad spacing. \$\endgroup\$ – Peter Taylor Apr 7 '17 at 10:05
  • \$\begingroup\$ Only the last one is valid. \$\endgroup\$ – Comrade SparklePony Apr 7 '17 at 13:25
  • \$\begingroup\$ The latest wording "only sentences with exactly two asterisks in them" suggests that there's no need to filter: just split on ., trim, and prepend Vocabulary word: to each sentence. \$\endgroup\$ – Peter Taylor Apr 7 '17 at 21:03
2
\$\begingroup\$

Base 32 RFC 4648 Compliant Alphabet!

When writing my handy-dandy totp/hotp token implementation in Python and Swift (ad: here), I encountered for the first time RFC 4648. There is a nice and long memo about RFC 4648, but I only had to focus on a very specific part of it: Page 8. If you are bored and want some enthralling reading, you can find this memo here, and a useful table here.

Basically, I was looking for the alphabet that could be used when base 32 decoding a String. Well, this is it: ABCDEFGHIJKLMNOPQRSTUVWXYZ234567, and padding, =. However, simply printing that is not the challenge –– that would be too simple1. Instead, we are going to print this (the comments are for your reference and do not need to be printed):

__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x00 - 0x0F or   0 -  15
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x10 - 0x1F or  16 -  31
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x20 - 0x2F or  32 -  47
__,__,26,27, 28,29,30,31, __,__,__,__, __, 0,__,__,  // 0x30 - 0x3F or  48 -  63
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x40 - 0x4F or  64 -  79 
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x50 - 0x5F or  80 -  95
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x60 - 0x6F or  96 - 111
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x70 - 0x7F or 112 - 127
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x80 - 0x8F or 128 - 143
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x90 - 0x9F or 144 - 159
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xA0 - 0xAF or 160 - 175
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xB0 - 0xBF or 176 - 191
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xC0 - 0xCF or 192 - 207
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xD0 - 0xDF or 208 - 223
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xE0 - 0xEF or 224 - 239
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xF0 - 0xFF or 240 - 255

There may be trailing spaces after every line, and trailing newlines after the last one.

Also, the single digit numbers can be written as 0[digit] instead of [space][digit]. However, be sure to include the spaces between the four groups.

By the way, the __ actually represent 255, but the former do not make me drown in a sea of digits.


1 Should the challenge be to just print that string?

Any other suggestions to make this challenge more interesting?

| |
\$\endgroup\$
  • \$\begingroup\$ Perhaps get a list of characters (of any length) and print such a table? \$\endgroup\$ – ugoren Jul 29 '17 at 19:14
2
\$\begingroup\$

Is this 2048 board valid?

Some 2048 boards are impossible to get into. For example,

2 _ _ 2
_ _ _ _
_ _ _ _
2 _ _ 2

will never occur in a 2048 game. Additionally, these are all impossible:

8 _ _ 8    8 _ _ _    2 2 2 2
_ _ _ _    _ 8 _ _    2 2 _ _
_ _ _ _    _ _ _ _    _ _ _ _
8 _ _ _    _ _ _ _    _ _ _ _

Your program needs to accept a 2048 board, and return a truthy value if the board is reachable, else falsy.

//Explanation of 2048 goes here.

I've listed 4 different boards that cover major test cases. Are there any others I'm missing?

| |
\$\endgroup\$
  • \$\begingroup\$ hehe, don't forget [tag:sliding-puzzle] \$\endgroup\$ – Stephen Aug 1 '17 at 19:56
  • \$\begingroup\$ As you've stated yourself the main thing missing here is the bulk of the challenge. \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 9:14
  • \$\begingroup\$ I wonder if it suffices to look one step back, or if you need to check if the previous position can itself be produced. \$\endgroup\$ – xnor Aug 4 '17 at 7:35
2
\$\begingroup\$

Smooth Usage [On hold while alternative scoring is considered]

We've all seen CPU usage graphs like this one:

CPU Usage example

Doesn't that look ugly? It would look much nicer as a lovely smooth sine wave...


Challenge

Write a program in the language of your choice that will infinitely produce a regular sine wave in Task Manager's (or Activity Monitor's if that's your thing) CPU usage graph.

You may assume:

  • Background CPU usage is constant
  • Only a single core must display the pattern
  • The system has sufficient cooling to prevent thermal throttling
  • Features such as Intel TurboBoost are disabled

This is tagged as to encourage short answers, but ultimately will be a as I suspect perfect solutions will be hard to come by.

| |
\$\endgroup\$
  • \$\begingroup\$ Related: stackoverflow.com/questions/551494/… \$\endgroup\$ – MTCoster Aug 11 '17 at 15:14
  • \$\begingroup\$ code-golf and popularity-contest don't mix together. You have to choose one or the other, but making it strictly code-golf would be difficult because you'd have to define what is a good enough sine wave, but on the other hand popularity contests are very risky to do. \$\endgroup\$ – dzaima Aug 11 '17 at 15:16
  • \$\begingroup\$ @dzaima That was exactly my dilemma - which would you suggest fits the challenge best? \$\endgroup\$ – MTCoster Aug 11 '17 at 15:17
  • \$\begingroup\$ I'd say a scoring algorithm of some sort would be best for this, no idea how you'd do it. Like the related one was objective. If you could read the word, it was valid. With this, is a bumpy sin-wave a sin-wave? \$\endgroup\$ – Magic Octopus Urn Aug 11 '17 at 20:39
  • \$\begingroup\$ @MTCoster If you're not sure whether popularity-contest fits, then you can be sure that it does not. It is quite difficult to make an well received one. Go with code-golf or make a code-challenge if you can come up with a good own winning criterion. \$\endgroup\$ – flawr Aug 11 '17 at 20:53
2
\$\begingroup\$

Time bomb ping pong


Challenge - Both teams

All users are divided into two teams based on their PPCG ID. For example, my ID can be found here, from which you can see that my ID is 34388. To check on which team you are, run the following snippet:

function update_team(){var e=document.getElementById("user-id").value,t=(document.getElementById("team-result"),"");t=e.match(/^\d+$/)||0===e.length?-1!==even_top_50.indexOf(parseInt(e))?"You are in team: ALPHA":-1!==odd_top_50.indexOf(parseInt(e))?"You are in team: BETA":0==e.length?"":"You are in team: "+(parseInt(e)%2==0?"ALPHA":"BETA"):"ID must be numeric",document.getElementById("team-result").innerHTML=t}var even_top_50=[12012,20260,17602,11259,26997,194,31716,20080,58563,47066,1426,4098,30688,56656,41723,3967,1490,31516,40695,29577,43319,15599,32686,3191,4020,67,34718,41024,7311,39328,16766,7110,31625,2867,59107,52210,16120,6710,68942,10740,9365,84,1147,15,199,7162,1308,3103,26600,59487],odd_top_50=[8478,36398,21487,3808,42545,3852,53748,48934,34388,21348,4162,34531,25180,31414,24877,31957,20469,31343,7416,45941,32014,39242,42963,11006,6828,9498,9288,14215,4198,3544,30164,33208,4372,95,41805,56178,668,47120,30525,55735,51507,57100,6699,737,39022,46855,51939,32700,59376,7209];
.main-header,.main-input,.result{font-family:Montserrat,sans-serif;text-align:center}.main-header{font-size:24px}.main-input{display:block;margin:12px auto auto}.result{margin-top:24px}
<br><div><div class="main-header"> Enter your PPCG ID </div><input class="main-input" maxlength="6" onkeyup="update_team()" id="user-id"> <div class="result" id="team-result"> </div></div>

Each user has two options:

  • Start a new bomb
  • Perform a counterattack

These actions are discussed here:


Start a new bomb

To set up a new bomb, you need to do the following:

  • Create a full program in any free language which has the output X.
  • Create a custom list of characters with a maximum of 10 characters.
  • Select one or more characters from the character list and insert them into your program, which will be having the exact same output X. This ensures that there is at least one crack for your submission.
  • Only reveal the full original program and the character list. Keep the modified program secret. Also keep track of the iteration index, which in this case is 1 (since it's the start of a new bomb).

This is an example of a new bomb submission:


Python 2, 9 bytes (index = 1)

Outputs the number 30.

print 5*6

With as character set 13579/. Try it online!.



Perform a counterattack

To perform a counterattack, you need to do the following:

  • Create a new full program with at least one character inserted from the list given by the opponent, which will have the exact same output X.
  • Create a custom list of characters with a maximum of 10 characters.
  • Select one or more characters from the character list and insert them into your program, which will be having the exact same output X. This ensures that there is at least one crack for your submission.
  • Only reveal the full original program and the character list. Keep the modified program secret. Also keep track of the iteration index, which in this case is the increment of the previous index.

This is an example of a counterattack (using the previous submission):


Python 2, 12 bytes (index = 2)

Defuses Python 2, 9 bytes, Adnan.

Inserts 1, / and 3. Outputs 30:

print 15*6/3

With as character set: +-~58. Try it online!



Scoring system

Every bomb that has not been defused for 7 days gives the team 'index' points. If the index was 4, your team gets 4 points. You are only able to collect the points after you have revealed your own solution. Note that if you do not reveal your solution after the 7 days, it is still vulnerable to cracks.

As for the individual winner of the team, the person with the most cracks of the winning team gets the check mark.


Sandbox notes

  • Note that this is more of an experimental challenge. Unlike the conventional 1 vs 1 cops-and-robbers challenges, this is an attempt on an n vs n-challenge, so I have no idea whether this is a good idea or not.

  • The scoring system is a bit tricky, but I think that when a bomb has 'exploded', the opponent's team gets (index) points. The team with the most points at the end wins. The problem here is that the byte count might make things worse, since a larger program would make cracking the submission harder.

  • A problem I'm finding here is the fact that the cop can create an arbitrarily large program, which makes it almost impossible to crack. I'm not sure whether this actually is a problem, since the 'exact same output'-rule should theoretically take care of this.

  • Perhaps add a third option for the user, where the user defuses a bomb. This would consist of cracking the submission, but does not create a counterattack (for cases when this is impossible, or trivial (like adding comments)).

  • I'm also not entirely sure about the 'choose your own output'-idea. Would this leave too much options for abusement?

  • Is the maximum of 10 character too much / too little? Should this also be taken in account with the scoring?

Thanks in advance!

| |
\$\endgroup\$
  • \$\begingroup\$ Maybe try the wording "one or more" instead of "at least one"? It took me a while to realise that was what you meant. For more meaningful feedback about diffusions/maximums I think you'd have to decide on a scoring mechanism first. Since both teams use the same bombs to advance their score I don't think the byte count think is that big of a problem? \$\endgroup\$ – FryAmTheEggman May 27 '17 at 0:38
  • \$\begingroup\$ @FryAmTheEggman Thank you for your response. I have decided that the score is just simply the sum of all index numbers of the bombs that aren't diffused after three days. This encourages counterattacks more, since the score will increment after each counterattack. \$\endgroup\$ – Adnan May 27 '17 at 9:34
  • \$\begingroup\$ Nice. A never-ending hot potato game. \$\endgroup\$ – Matthew Roh May 29 '17 at 12:27
  • \$\begingroup\$ @SIGSEGV Yeah, that's what it's supposed to be. I should probably set a time limit somewhere, otherwise there will be no winner at all :p. \$\endgroup\$ – Adnan May 29 '17 at 13:07
  • \$\begingroup\$ I'm worried that this could very easily turn into "stay online more than your opposition does", if an answer is given in a language that's very easy to crack. \$\endgroup\$ – user62131 May 31 '17 at 22:47
  • 3
    \$\begingroup\$ 1. Defuse, not diffuse. 2. Three days is not much. A carefully timed post at the start of the weekend could slip through the net. 3. Unless I missed it, there's nothing to prevent the usual CnR-killer crypto answer. Are you absolutely certain that they won't break the challenge? \$\endgroup\$ – Peter Taylor Aug 21 '17 at 12:51
  • \$\begingroup\$ @PeterTaylor Thanks for your response. I have changed the time limit to 7 days. The main problem would indeed still be cryptographic submissions. I tried to decrease the severity of this problem by making sure that the output would remain exactly the same before and after modifying the submission, but I need to experiment a bit with this to see how this would end up. Hashing would almost certainly not be possible, unless a hashing algorithm is cracked (but I'm not 100% certain about this). \$\endgroup\$ – Adnan Aug 21 '17 at 13:06
  • \$\begingroup\$ As for the hashing, this worked for me: "Please, don't "implement RSA" or anything mean to the robbers. Use obscure languages and features, not boring encryption and hashing. I can't enforce this with rules, but you can expect torrential downvotes if all you do is sha(input) === "abcd1234"." \$\endgroup\$ – programmer5000 Aug 24 '17 at 14:33
2
\$\begingroup\$

Conversion: 2 dice from 3


This fascinating video from Matt Parker's standupmaths poses a challenge:

Given the result of rolling 3 indistinguishable (unordered) dice, simulate the result of rolling 2 indistinguishable (unordered) dice.

For the purposes of this challenge, simply returning the sum of 2 dice is not sufficient. Returning 2 ordered dice is acceptable, as the order can be ignored so this still fulfils the requirement.

Input

Either 3 unordered values from 1 to 6, or 3 ordered values from 1 to 6. If the values are ordered, then the output must be independent of the input order. For example, the input 1, 2, 3 should give the same output as the input 2, 1, 3.

These are standard dice. Your code may not assume the values will be from 0 to 5 instead of 1 to 6.

Output

Either 2 unordered values from 1 to 6, or 2 ordered values from 1 to 6. If the values are ordered, then different orderings will be considered equivalent. For example, output 1, 2 is equivalent to output 2, 1.

Given input that matches the probability distribution of rolling 3 dice, the probability distribution of the output must match that of rolling 2 dice.

You can choose to calculate the outputs however you wish, provided that they are deterministic (the same input in any order gives equivalent output). That is, different answers may use different mappings. So for input 1, 2, 3, one answer may give output 4, 5, while another answer may give output 5, 6. Provided all outputs occur in the correct proportions, both answers are valid.

The output must also use standard dice. Your code may not output values from 0 to 5 instead of 1 to 6.

Checking for correctness

One simple but laborious way of checking that the outputs occur in the correct proportions is to consider all 216 possible ordered triples as inputs. This automatically accounts for the fact that the unordered triple 1, 2, 3 is 6 times more likely to come up that the unordered triple 1, 1, 1, since it will occur as 6 different ordered triples (the 6 different ways of arranging 1, 2, and 3).

A valid answer will give the same output (apart from order) regardless of the order of the input, and will give any given double such as 1, 1 for exactly 6 of the ordered inputs, and any given distinct pair such as 1, 2 (equivalently 2, 1) for exactly 12 of the ordered inputs.

Scoring

The original puzzle was asking for an easy way for humans to calculate this in their heads during playing a game. This challenge is instead , so the score is the number of bytes in your code, and the lowest score in a given language wins.

Prior work

This was also posted on puzzling.SE and there are a number of approaches there. Although they are aimed at being human usable, there may be some insights there that are relevant to writing short code.

Test cases

As every answer may use a different mapping, there is no way to generate meaningful test cases for this challenge. The simplest way I can think to test is as described above under "Checking for correctness".


Sandbox questions

  • I've just discovered this previous challenge which is based on the same video. It asks only for the sum of 2 dice, rather than an unordered pair, so is not identical. Is this a sufficient difference to avoid this being a duplicate, and would it be different enough to be worthwhile posting?
| |
\$\endgroup\$
  • \$\begingroup\$ Even if it's not officially a dupe I'd still like feedback on whether it's different enough to be interesting. \$\endgroup\$ – trichoplax Aug 23 '17 at 15:45
  • \$\begingroup\$ Looking at the Jelly answer, I think the change required for this question is to remove the final character. So yes, it does fail the dupe test. \$\endgroup\$ – Peter Taylor Aug 23 '17 at 21:35
2
\$\begingroup\$

Is this a valid Takuzu board?

Takuzu is a logic game in which you have to complete a grid with cells containing 0s and 1s. The grid must follow 3 rules:

  1. No three horizontal or vertical cells in a row can be the same.
  2. There must be an equal number of 0s and 1s in each row and column.
  3. No two rows can be the same, and no two columns can be the same.

Let's look at a finished grid:

0011
1100
0101
1010

As you can see, this board follows rule 1, 2 and 3. There are no three horizontal or vertical cells that are the same, all the rows and columns contain an equal number of 0s and 1s, and no two rows and no two columns are the same.

Let's look at a grid that isn't valid:

110100
010011
011010
101100
100011
001101

There's a bunch of problems with this grid. For example, row 5 has three 0s in a row, and column 2 has three 1s in a row, followed by three 0s. Therefore, this is not a valid grid.

Task:

Your task is to make a program which, given a 2D array of n * n 0s and 1s, verifies the board to see if it's a valid, finished Takuzu board.

Examples:

0011
1100
0101
1010

This board follows all the rules, and is therefore a valid Takuzu board. You must return a truthy value for this.

11
00

This is not a valid board - row 1 doesn't follow rule 2. You must return a falsey value for this.

Rules and Specs:

  • You can assume that all boards are square of dimensions n * n, where n is a positive even integer.
  • You can assume that all boards are finished.
  • You may take input as a 2D array containing values signifying 0 and 1, or as a string.
  • You must output consistent truthy and falsey values for truthy and falsey boards, and the values representing "truthy" and "falsey" cannot be the same.

This is , so shortest code in bytes wins!

| |
\$\endgroup\$
  • \$\begingroup\$ 1. "No three horizontal or vertical grids in a row can be the same": there's only one grid. I propose rewording as "No horizontal or vertical line of three cells can be the same". 2. Related: codegolf.stackexchange.com/q/68646/194 , codegolf.stackexchange.com/q/118856/194 . Note that because this question works through a long example before stating very briefly that (in essence) the example is irrelevant to the question, it can very easily mislead people into thinking it's an exact dupe of the second of those related questions. \$\endgroup\$ – Peter Taylor Aug 27 '17 at 16:49
  • \$\begingroup\$ ...also note that the example you run through before giving the task can actually be performed by only using rule (2). \$\endgroup\$ – Jonathan Allan Aug 29 '17 at 6:47
  • \$\begingroup\$ @PeterTaylor Will fix the example and other points, I wasn't active for a while, sorry for the late reply. \$\endgroup\$ – clismique Aug 29 '17 at 6:48
  • 1
    \$\begingroup\$ @JonathanAllan Through fixing PeterTaylor's suggestion I also fixed yours :P \$\endgroup\$ – clismique Aug 29 '17 at 6:53
  • \$\begingroup\$ By "You must output distinct truthy and falsey values for truthy and falsey boards" do you mean "consistent" ones - i.e. the Truthy (falsey) value is to be the same for each time a valid (invalid) board is input? The normal definition of Truthy vs Falsey is language dependent: any values that conditionally evaluate as such (i.e. such that the equivalent of the pseudo-code if myVal then print("True!" else print("False!") works as expected). \$\endgroup\$ – Jonathan Allan Aug 29 '17 at 7:05
2
\$\begingroup\$

Align the Words

Given a list of words l output them as follows:

  • Iterate through l, if it's the first word, output it as usual.
  • If it's not the first word, iterate through this nth word and:
    • Find the first letter of word n that's in word n-1.
    • Align the first occurrence of that letter in word n with the first occurrence in word n-1 and print it on the next line.

Worked Example

Input: [ace,face,please,keep,sheeple]

1: ace

2:  ace
   face

3:  ace
   face
    please

4:  ace
   face
    please
     keep

5:  ace
   face
    please
     keep
    sheeple

[Note: You only print step #5, the rest is to show the process.]

Rules

  • Lowest byte-count wins, this is .
  • All consecutive words in the input list l will have at least 1 letter in common.
    • If the input is invalid, any return is fine (error, nothing, etc...)
  • A word is defined here as a collection of a-z (lowercase ONLY alpha characters).
| |
\$\endgroup\$
  • \$\begingroup\$ Related, not a dupe. \$\endgroup\$ – AdmBorkBork Sep 11 '17 at 18:48
  • \$\begingroup\$ To be clear, are we to output every step along the way, or just the final arrangement? If every step along the way, what's an appropriate separator? \$\endgroup\$ – AdmBorkBork Sep 11 '17 at 19:04
  • \$\begingroup\$ @AdmBorkBork final product, should make that clear I s'pose. \$\endgroup\$ – Magic Octopus Urn Sep 11 '17 at 21:13
  • \$\begingroup\$ Are we allowed to use uppercase only instead of lowercase only as well? Not really relevant for the programming language I usually golf in, but I can imagine it's relevant for some programming languages. \$\endgroup\$ – Kevin Cruijssen Sep 26 '17 at 12:00
2
\$\begingroup\$

100 Letters is the Perfect Amount

Oxford dictionary lists the most commonly used English letters in the following order:

EARIOTNSLCUDPMHGBFYWKVXZJQ

And assigns each the following frequencies:

Distribution of the letters...

For the purpose of this challenge, the diagram will be simplified as follows:

z   1
q   1
x   1
j   1
k   1
v   1
b   2
p   2
y   2
g   2
f   2
w   2
m   3
u   3
c   3
l   4
d   4
r   5
h   6
s   6
n   6
i   6
o   7
a   8
t   9
e   12
TOT 100

Now, onto the task at hand; I've provided you all with a dictionary of words to choose from, using this dictionary of words choose as many as you want to output. However the catch is that you must have EXACTLY the count above of each letter in the output using 7-12 words.


Scoring

  • Your base score is the length of your code in bytes.
  • You are allowed to go over or under on the number of letters required, each letter above or under results in a +5 byte penalty.
  • If the number of words you've used is between 7 and 12, no penalty is incurred.
    • IF it exceeds 12, add 10 bytes per additional word.
    • IF it is less than 7, subtract 5 per missing word.

Rules

  • You may use any word from the provided dictionary.
  • Each word you output must be distinctively separated by either a space or a newline.
  • Once a word combination has been posted, you may not use more than 6 of that answer's words together in a new answer.
    • This will be enforced by post date.
  • This is
  • Your score will be as defined in the scoring section.
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ How can you get a meaningful penalty for going under the number of letters required when you must have AT LEAST the count above of each letter? \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 0:21
  • \$\begingroup\$ Also, who was Kolmognogniznornia? \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 0:22
  • \$\begingroup\$ @JonathanFrech he was the first Aztec man to invent the concept of speech. \$\endgroup\$ – Magic Octopus Urn Sep 19 '17 at 0:30
  • 2
    \$\begingroup\$ I'm not sure this is really kolmogorov-complexity: by design, a good answer will be incompressible. However, finding a good answer is going to involve a heavy computer search, and then the posted answer is going to be a string literal. That seems completely backwards: the interesting code should be what the question asks for. \$\endgroup\$ – Peter Taylor Sep 19 '17 at 7:39
  • \$\begingroup\$ @PeterTaylor was kinda going for something more unique, y'know? Sorta like my "5 favorite letters" challenge. \$\endgroup\$ – Magic Octopus Urn Mar 13 '18 at 20:47
2
\$\begingroup\$

Implement a BrainFlump interpreter

BrainFlump is the latest alternate memory model brainfuck-esque turing tarpit.

It operates on a memory model we call a "Dump", which is simply an un-ordered collection of integers, with a pointer indicating the current item to operate on. As it is "unordered", when moving to the next item, one is simply chosen at random (chosen uniformly between the items that are not the currently selected item) and the operation pointer is moved to that item.

Commands

+   #Increment the item at the pointer
-   #Decrement the item at the pointer
:   #Add a 0 to the dump, and move the pointer to it
;   #Move the pointer to a random item that is not the pointer's current position
(   #Skip to the matching ) if the item at the pointer is 0
)   #Skip to the matching ( if the item at the pointer is not 0
,   #Read a single character from STDIN and push its ascii value to the dump
    #This also moves the pointer to the new item
.   #Print the current item at the pointer modulo 127 as an ASCII character

Interpreter or Compiler?

BrainFlump is an interpreted language. Meaning your submission must take BrainFlump code as input, and return the expected output of the code.

This is as opposed to a compiler, which would take BrainFlump code as input, and return a compiled binary that returns the expected output.

Other notes

  • When the ; command is used if the dump contains only 1 item, a new 0 is pushed to the dump, and the pointer is moved to it
  • The . command does not pop the item from the dump
  • When the , command is used if STDIN has been exhausted, a new 0 is pushed to the dump, and the pointer is moved to it
  • Any item in the dump who's value is 0 is not considered to exist, unless it is the item at the pointer, therefore to "pop" an item from the dump, you simply set its value to 0
  • Nested loops are supported
  • The random number generator used for the interpreter does not have to be cryptographically secure, but must chose with uniformity.
  • BrainFlump does not support floating point numbers or negative integers. Attempting to decrement a number below 0 has no effect.
  • The maximum value of an item in the dump is 255

Examples/Testcases

brainf**k emulation

++++++(;++++++++;-);.

This should output 0

Explanation

++++++        #Increment the first item to 6
(             #While the item under the pointer is not 0
    ;         #Move to another item in the dump
              #    Note the first time this loop runs,
              #    this will insert a new item
    ++++++++  #Increment the new item by 8
    ;         #Switch to another item in the dump
              #    Note there are only 2 items currently,
              #    So this will switch to the only other
              #    item, the one we initially incremented to 6
    -         #Decrement the item
)             #Repeat the loop if the item is not 0
;             #Switch to the other item
              #    Note this switches the pointer back to
              #    The item we have been incrementing by
              #    8 each loop
.             #Output as ASCII character

This is effectively a 6*8 operation, followed by an output, and is nearly identical to brainf**k's ++++++[>++++++++<-]>. program, which also outputs 0.

Note, however, that brainf**k-esque dump manipulation is only deterministically possible if there are never more than 2 items in the dump.

Random output

+:++:+++:++++:+++++:;.

This will actually always output an unprintable character, however which character is output will be random each time, selected from: SOH, STX, EST, EOT, ENQ, ie ASCII characters 1-5. In a correctly implemented interpreter, this output should be uniformly random between the 5 possibilities.

Explanation

+      #Increment first item to 1
:      #Add new item and move to it
++     #Increment new item to 2
:      #Add new item and move to it
+++    #Increment new item to 3
:      #Add new item and move to it
++++   #Increment new item to 4
:      #Add new item and move to it
+++++  #Increment new item to 5
:      #Add new item and move to it
       #    Note this last item is added because ; will
       #    always switch to an item that is *not* the
       #    currently selected item
;      #Switch randomly to an item in the dump
.      #Output as ASCII character

To give a little more info on this, by the time the ; command is reached, the dump should look like this:

1 2 3 4 5 0
          ^

As ; always switches to a different item, the result will be the pointer at one of the non-zero items.

cat

,(.,)

Nice and simple, and identical to brainf**k's cat program.

For scoring purposes, you should use this gist as input when testing.

When will it end?

++++(,:+++++;++(;++++++;--):++++;---)

This program doesn't output anything, but runs for a non-deterministic amount of time.

Explanation

++++             #Increment first item to 4
(                #Start loop
    ,            #Read char from STDIN to new item in dump
    :+++++       #Push 5 to dump
    ;++          #Switch to random item in dump and add 2
    (            #Start loop
        ;++++++  #Switch to random item in dump and add 6
        ;--      #Switch to random item in dump and subtract 2
    )            #End loop
    :++++        #Push 4 to dump
    ;---         #Switch to random item in dump and subtract 3
)

This one is a little tricky, as ; will never switch to a 0 (Remember items with a value of 0 are considered to not exist)

The inner loop will only exit if ;-- switches to a number <= 2

The outer loop will only exit if ;--- switches to a number <= 3

Due to the inherent randomness of the language, this should always terminate... eventually.

For scoring purposes, you should use the exact string Hello, World! as input when testing.

Scoring

This is meaning the interpreter that on average runs the fastest, wins!

Scoring will be determined by running each of the 4 test-cases above 100 times, and determining an average runtime (due to the inherent randomness of the language, a high number of runs should be made to minimise anomalous results).

Then once you have an average for each testcase, sum the 4 times, and that is your final score. Lower is better

| |
\$\endgroup\$
2
\$\begingroup\$

Count bicubic graphs

This question assumes basic knowledge of graph theory terminology.

A cubic graph is a simple graph whose vertices each have exactly 3 edges. A bipartite graph is a vertex whose vertices can be divided into two disjoint sets such that every edge is between a vertex in one set and a vertex in the other set. A bicubic graph is a graph which is both cubic and bipartite.

It is easy to show that a bicubic graph must have the same number of vertices in each of the bipartite halves, so the number of vertices must be even. It is also easy to show that it must have at least six vertices. The only bicubic graph with six vertices (up to isomorphism) is the so-called utility graph or K3,3:

The edges are the Cartesian product of two three-element sets of vertices

Input

A positive non-zero integer n.

Output

The number of bicubic graphs with 2n vertices, up to isomorphism.

Notes

  • The graphs are not required to be connected.
  • This sequence is OEIS A008325. However, hard-coding these values will be considered a breach of standard rules. You may hard-code for inputs of up to 3, but above that the code should follow the same paths and be correct assuming unbounded memory and time for any valid input. It seems unlikely that we will extend the sequence, but it's nonetheless a worthy stretch goal.

Test cases

Input  Output

1      0
2      0
3      1
4      1
5      2
6      6
7      14
8      41
9      157
10     725
11     4196
12     29816

Winning criterion

The fastest program wins. The primary win condition is the largest input for which correct output is given within 10 minutes. In case of ties, the time taken to compute the value for that input will be compared. If the difference is less than 20 seconds, the earlier answer wins.

| |
\$\endgroup\$
2
\$\begingroup\$

All ASCII Art

Input

You will be given a set of x, y, and A pairs, where x and y represent a coordinate on a 2-d plain, and A is some character. You may take these pairs in any convenient format, e.g. a list of lists, three separate lists, a list of pairs of lists, etc.

Output

You will output a grid of spaces. However, at every coordinate specified in the input, the space should be replaced by the character. Basically, the input specifies the locations of characters, and you have to draw them.

Specifics

  • x and y may be either a coordinate or a row-column pair (e.g. the origin can be in the bottom left, with x increasing to the right and y increasing up, or the origin can be in the top left, with x increasing to the right and y increasing down).
  • All characters are guaranteed to be printable ASCII, and will never be a space.
  • x and y are >= 0
  • You may output trailing whitespace (but not infinitely). What matters is that the output visually looks like what the input specified, not the whitespace.

Test Cases

Test cases format (the test cases have the origin at the top left corner; this is optional, see specifics):

# of coordinates
row col char
row col char
...
-----------
output

Test cases:

2
0 0 :
0 1 )
-----------
:)

3
0 0 -
0 1 _
0 2 -
-----------
-_-

4
0 1 -
1 0 |
2 1 -
1 2 |
-----------
 - 
| |
 - 

11
0 0 (
0 1 ^
0 2 o
0 3 ^
0 4 )
1 1 /
1 2 |
1 3 \
2 2 |
3 1 /
3 3 \
-----------
(^o^)
 /|\
  |
 / \

Here is a Java program which can be used to test out inputs

Meta

| |
\$\endgroup\$
  • \$\begingroup\$ Is (0,0) the top-left of the output image? It kinda looks that way from your examples, but that should be made clear. \$\endgroup\$ – AdmBorkBork Nov 3 '17 at 12:30
  • \$\begingroup\$ @AdmBorkBork it is for the test cases, but its meant to be optional... I'll clarify \$\endgroup\$ – Socratic Phoenix Nov 3 '17 at 12:43
2
\$\begingroup\$

RaceTrack Arena KOTH

(haven't come up with a very good title)

this koth is inspired by the pen and paper game Racetrack.

RaceTrack Movement

Racetrack (and this racetrack-inspired koth) use a distinctive vector based movement system.

all bots players are on a square grid.

initially, a cycle (this is what we will call bot players) will have no movement i.e. be completely motionless

However, after a cycle begins moving, it gains inertia; it will not stop moving in this direction unless it acts to stop moving.

On every turn, a cycle can change their speed on each axis (x and y) by -1, 0, or 1, and the same with y speed. this includes sticking with their current speed. This means that every turn, a cycle has 9 options of spaces to move to (excluding spaces which would cause them to crash)

enter image description here

for example, in this diagram, the cycle indicated by the red space, which has just moved from the brown space, has the option of the 9 green squares in the red-lined area, the main, more saturated, green square, along with the blue line, represents where it will end up staying on its inertial course

if, for some reason, the cycle wanted to come to a complete stop, it would take 5 turns, which is the Chebyshev distance between the inertia vector's end and the cycle.

[more tbd obviously]

don't downvote for the lack of content please

| |
\$\endgroup\$
  • \$\begingroup\$ Can (like on the paper) every contestant see the whole arena, including other contestants' movements? As I remember, it's alternative moves rather than simultaneous and you crash if you end up on or cross other contestant's position or most recent motion line. How will the edge be defined? You crash if you end up outside OR if your motion line crosses outside area. Explain the rules in your post. You can have different rules, but if you keep alternative move the starting player will have advantage. So every contestant of this KOTH should have equal number of participation at each position. +1 \$\endgroup\$ – Heimdall Nov 11 '17 at 8:36
  • \$\begingroup\$ We don't know the first player has so much of an advantage; random positions are rather likely to have a much larger effect than the fact that player 1 can strategy steal, and even with non-randomised positions, playing with multiple players is very different in flavour from just two players, since playing against one player, their moves only make themselves better or worse, but in multiplayer another (dumb) player can unwittingly help you or harm you without regard to whether it does help them. Also I haven't decided on whether bots can see the whole playing field or if they have a top speed \$\endgroup\$ – Destructible Lemon Nov 12 '17 at 22:53
  • \$\begingroup\$ ... if there is a limit to their sight, it follows there has to be a limit to their speed, and even if there isn't an implemented, it's at least effectively a limit, since moving somewhere you can't see if there is a wall is not a great strategy. also there will probably be obstacles that act like walls, so the edge is not the only place to crash, btw. anyway, the definition of crash, is that a bot's movement line goes through a hazardous square. I suppose that touching a vortex can be considered a near miss \$\endgroup\$ – Destructible Lemon Nov 12 '17 at 22:55
  • \$\begingroup\$ that said, I guess there's no real reason not to randomise the turn order each game. \$\endgroup\$ – Destructible Lemon Nov 12 '17 at 23:09
  • \$\begingroup\$ Suppose you're the first, whatever your starting position. You accelerate so that you have maximum safe speed. Others won't accelerate to higher speed because that would cause them to crash at the turn (unless, as you put it, a dumb racer decides to overtake you anyway). Let's say the next turn is left. You'll go as far left as possible. Racers on your right will just lag behind. But racers on your left will only be able to keep up until you "cut the corner". They won't be able to stop you from doing so because at no point they will be ahead of you. But maybe some random debris on the path ... \$\endgroup\$ – Heimdall Nov 13 '17 at 10:49
  • \$\begingroup\$ Actually, dumb racing might be a good strategy... If you are allowed to have more than one bot in a race, one can be "dumb" to increase the other one's chances... \$\endgroup\$ – Heimdall Nov 13 '17 at 10:52
  • \$\begingroup\$ @Heimdall that strategy tends to be discouraged. making a simple bot is not, but making bots collude is frowned upon. \$\endgroup\$ – Destructible Lemon Nov 13 '17 at 23:33
  • \$\begingroup\$ So I guess the wall is made by placing a series of hazardous squares, and crashing means you're out of that race only. But how is crash between two racers defined and dealt with? \$\endgroup\$ – Heimdall Nov 16 '17 at 7:12
  • \$\begingroup\$ @Heimdall no offence, but I haven't actually made enough of the spec that I should be answering questions from you in the comments, especially since you have a rather inaccurate idea of the game (because i haven't specified). for example, it's not a race. \$\endgroup\$ – Destructible Lemon Nov 16 '17 at 8:29
  • \$\begingroup\$ Sorry, I'm a bit impatient. It's just I'm looking forward to your game which is still in the making, that's why I gave it +1. I assumed it was a race (or series of races) where the bots compete because it's based on that paper race. Also I was trying to be helpful by raising potential issues in order for the task to be well formed. \$\endgroup\$ – Heimdall Nov 16 '17 at 10:27
2
\$\begingroup\$

Bunnies in (three-dimensional) space

A panicked call has come in from the International Space Station: a psychological experiment has gone awry, and the astronauts have lost all their Stanford Bunnies. You have been tasked to come up with a way to get them as many replacements as possible.

 

a description of the plan

 

Because of the rush, NASA has just one rocket available for this mission: a Delta II Heavy with a box-shaped cargo hold (a "right cuboid", they called it) of length x, width y and height z, all even integers. Your job is finding out how many bunnies to bring - and how to pack them.

Input and output

Your program should take the dimensions of the cargo hold as arguments. It should then compute how many bunnies it can fit in there, producing output as follows:

  • A header line consisting of the length, width and height of the box, as integers, seperated by spaces. This is a copy of the input.
  • A line for every bunny fitted, containing the following as dotted floats, all seperated by spaces:
    • the position of the center of the bunny, relative to the center of the box, as x, y and z
    • the rotation of the bunny, as a rotation about the x, y and z axes, in that order (a.k.a. Tait–Bryan angles).

For example, a solution for a box of 4 × 6 × 8 units, with a single, un-rotated bunny in the center, would be described as follows:

4 6 8
0.0  0.0  0.0   0.0  0.0  0.0

A solution for a larger box of 12 × 8 × 8 units with two bunnies could look like this:

12 8 8
 4.5433 2.5843  1.4380 3.1415 0.0000 0.0000
-2.4839 1.3923 -1.9400 0.0000 0.0000 1.5707

...although your program will likely be able to fit more bunnies.

Dataset

This is the vertex data for the bunny. It is in Wavefront OBJ format, which means that every 'v' line describes a vertex (point in x, y, z space), and every 'f' line describes a triangle of vertices. Compared to the original Stanford Bunny model, this model has been translated so that its centerpoint is at the origin (0, 0, 0) and it fits snugly inside a unit cube.

Tips

  • You don't have to use the dataset above in your program - for example, you might want to simplify it more - but you should make sure that your output is correct when using the 'official' model.
  • Be careful with rounding, both during calculations and when outputting your result.
  • The Wavefront format can be imported into the free blender program if you want to see what it looks like (make sure to choose 'Z Up').
  • Your program does not have to be usable for other models: it can be a special-purpose bunny-fitting utility.

Rules and winner

  • A valid solution is one where, if you constructed a box of bunnies using the solution's description and the vertex data above, none of the bunnies would touch each other or the bounding box.
  • Your program has to be usable for box sizes other than the one below.
  • Your entry should run in less than, say, ten minutes on reasonable hardware.
  • The program must be self-contained: you can only use your language's standard libraries.
  • The winner is the program that succesfully fits the most bunnies in a box of 12 × 8 × 6. Include (a link to) your code, (a link to) a solution for that box size, and, if you made any, a picture of your solution.
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'd recommend against Unicode chars in the title. \$\endgroup\$ – Erik the Outgolfer Nov 17 '17 at 22:42
  • \$\begingroup\$ @EriktheOutgolfer Fixed! \$\endgroup\$ – Wander Nauta Nov 17 '17 at 22:43
  • 3
    \$\begingroup\$ Why only allowing the language's standard libraries? That seems like it would ban things like numpy for python, which may be useful for extra math functions. It's a standard loophole for people to make new libraries designed to solve a challenge anyway. \$\endgroup\$ – Rɪᴋᴇʀ Nov 18 '17 at 0:26
  • \$\begingroup\$ Also, is there a tie-breaker if 2 programs find the optimal solution? Shortest code? "Whoever submitted first" is likely fine but seems ugly to me, maybe fastest code? \$\endgroup\$ – Rɪᴋᴇʀ Nov 18 '17 at 0:29
  • \$\begingroup\$ @Riker: I added the self-contained rule to prevent people from grabbing an off-the-shelf implementation for the actual problem, or introduce wild dependencies that make it hard to reproduce results. You're right that numpy is generic enough that it could almost be considered part of the standard library, but I thought I had to draw the line somewhere. Do you think I should remove the rule altogether? \$\endgroup\$ – Wander Nauta Nov 18 '17 at 0:38
  • \$\begingroup\$ @Riker: A naive solution can fit 576 bunnies, and well-thought-out versions will likely score much much more, so I think the chance of two different approaches accidentally getting exactly the same score is quite slim. If there is an optimal solution (I'm actually not sure!) I'd be comfortable letting the first submitter to find it win. \$\endgroup\$ – Wander Nauta Nov 18 '17 at 0:47
2
\$\begingroup\$

Inside or Outside?

Given a point and a polygonial loop that is not self intersecting, determine whether the point is strictly inside or outside of the loop.

Details

  • The polygon is given as an ordered list of points cartesian coordinates.

  • The single point is given as a separate input, but you can also say that is e.g. always the first or always the last point in the list.

  • We only consider points with integral coordinates.

  • You can choose whatever representation is easiest to work with for you for instance a list of pairs, or two separate list for the x- and y-coordinates etc.

  • The list describes the polygon in positive orientation, that means the inside is always on the left side if you follow the points from the beginning to the end of the list. (You may choose to use the opposite orientation but please indicate if you do.)

  • A point is considered to be strictly on the inside, if it is not contained in the border of the polygon.

Examples

[(0,0),(0,2),(2,2),(2,0)]: (1,1) is strictly inside, all other points are outside
[(0,0),(0,2),(2,0)]: no point is strictly inside

more coming soon...

Meta:

  • Should I relax the strictly inside to just inside (i.e. a point on the border is also considered as inside)
  • Should I let the participants choose which version they prefer?
| |
\$\endgroup\$
  • \$\begingroup\$ 1. Not necessarily convex or must be convex? 2. What you describe as "positive orientation" is the same as "in counter-clockwise order". 3. Does the point for testing for inside/outside have integral coordinate? \$\endgroup\$ – user202729 Nov 26 '17 at 14:42
  • \$\begingroup\$ The shape is arbitrary and the testing point does have integral coordinates too (see examples) \$\endgroup\$ – flawr Nov 26 '17 at 14:46
  • \$\begingroup\$ Seems that you flipped what "positive orientation" means. Keep this if that is what you want. / Proposed test case: (0,0),(0,5),(2,2),(5,0) → strictly inside integer points = (1,1),(1,2),(1,3),(2,1),(3,1) where the shape is a concave quadrilateral. \$\endgroup\$ – user202729 Nov 26 '17 at 14:58
  • \$\begingroup\$ Well the first one was incorrect, positive actually means counter clockwise. \$\endgroup\$ – flawr Nov 26 '17 at 19:37
  • \$\begingroup\$ 4. Does the flexiblity in input extend to allowing us to require the first vertex to be repeated at the end of the list? 5. The strictly inside vs inside issue might be best addressed by asking for a classification into strictly inside, on the perimeter, and strictly outside. This is slightly trickier, I think, because of the implication that you can't cast a ray to infinity and just ignore edges which are parallel to it. \$\endgroup\$ – Peter Taylor Nov 27 '17 at 10:37
2
\$\begingroup\$

(No title currently)

Given a natural number N and a natural number K, find a list of natural numbers L such that:

  1. The product of the elements of L is N
  2. Each member of L is less than or equal to K
  3. And the length of L is minimized.

(You can return these numbers in any order.)

Note that:

  • If no such list exists, you program may do anything besides yielding a valid list, including but not limited to:
    • Printing something to stderr
    • Yielding an empty list
    • Yielding a non-list (see below)

If outputting to stdout, you can output a list in any reasonable fashion, such as:

  • Comma-separated: 3, 5, 7
  • With brackets: [3, 5, 7]
  • Whitespace-separated: 3 5 7
  • Your native list representation (3`4`5 or 3 4,5,, etc.)

Test cases (examples)

N, K -> L

32, 2 -> [2, 2, 2, 2, 2]
50, 10 -> [5, 10]
1224, 99 -> [72, 17] or [24, 51]
5, 10 -> [5]
1337, 100 -> []                         (since 1337 = 7 * 191)
1337, 191 -> [7, 191]
42, 8 -> [6, 7]
42, 21 -> [2, 21] or [3, 14] or [6, 7]
1, 2 -> [1]                             (NOT the empty list)
36, 6 -> [6, 6]
36, 9 -> [4, 9]
36, 12 -> [4, 9] or [3, 12]
32, 64 -> [32]
432, 9 -> [6, 8, 9]                     (NOT [2, 6, 6, 6])
216, 8 -> [6, 6, 6]                     (NOT [8, 3, 3, 3])
| |
\$\endgroup\$
  • \$\begingroup\$ (1) I think every instance of number needs to be replaced with natural number. Otherwise 1337, 100 can be satisfied by [sqrt(1337), sqrt(1337)] or [-1, -1337]. (2) Are any of the test cases failed by a greedy approach? If not, can you construct a test case for which a greedy approach fails? (3) What is the correct output for 1, 2? I can make a case for [], but I wonder whether you expect [1]. \$\endgroup\$ – Peter Taylor Nov 29 '17 at 16:10
  • \$\begingroup\$ @PeterTaylor (1) True. (2) I'm not entirely sure. (3) I think I will exclude the empty product as valid output \$\endgroup\$ – Conor O'Brien Nov 29 '17 at 17:19
  • \$\begingroup\$ @PeterTaylor I think 432 would not work with a greedy approach, can you confirm? [2,6,6,6] as opposed to [6,8,9] \$\endgroup\$ – Conor O'Brien Nov 29 '17 at 17:25
  • \$\begingroup\$ Aha. For (2), I think it's worth adding test case 216, 8. The greedy approach would be to say that 8 divides 216 and then split 216/8 = 27 as [3, 3, 3] giving a division into four factors; but [6, 6, 6] is a valid division into three factors. Edit: overlapped with your comment. I think you're attacking a different greedy approach. The more the merrier for test cases. \$\endgroup\$ – Peter Taylor Nov 29 '17 at 17:26
  • \$\begingroup\$ @PeterTaylor I see what you mean, thanks for the help! \$\endgroup\$ – Conor O'Brien Nov 29 '17 at 17:35
  • 1
    \$\begingroup\$ Why can there be a 9 in 432, 8? It violates the second rule. \$\endgroup\$ – NieDzejkob Nov 30 '17 at 21:14
  • \$\begingroup\$ @NieDzejkob Sorry, a typo on my part, thanks! \$\endgroup\$ – Conor O'Brien Dec 2 '17 at 2:19
2
\$\begingroup\$

Show a Chess Piece Range

Write a program or function that, given a set of movement rules, shows the available moves for a fairy chess piece.

Movement Rules:

This will use a slightly modified version of Parlett's Movement Notation:

A number, 1, 2, etc. shows how far a piece can move in a given direction. n indicates any distance, and two numbers separated by a hyphen (e.g. "1-4") means that there is a range of distances that the piece can move. Ranges may be enclosed in parentheses.

Numbers are followed by a direction sign:

  • * - any direction, orthogonally or diagonally
  • + - orthogonally (forwards, backwards, sideways)
  • X - diagonally
  • > - forwards
  • < - backwards
  • = - sideways
  • X> - diagonally forwards
  • X< - diagonally forwards

These directions can be combined, so <> means forwards or backwards, X= means diagonally or sideways, etc. Note that >X means forwards or diagonally, and is different from X>.

This gives us many of the standard chess pieces. For example, 1* is a King's movement, while nX is a Bishop.

There are also "grouping" indicators:

  • / - two numbers (or ranges) separated by a slash indicates a "hippogonal" move, like a knight: a/b means move a spaces orthogonally, and b spaces perpendicular to the first move. These may be enclosed in parentheses.
  • & - repeated movement in the same direction
  • . - "then" - combines two distinct moves, one after another.
  • , - "or" - separates two distinct moves. Only one may be taken on a turn.

The format of a move (not including grouping) is <distance><direction><other>.

Input:

A string showing the movement rules.

Output:

An ASCII representation of an 8x8 chess board with the given piece on the d4 square, with all other accessible squares indicated. For example, given the input n* (a queen), you should output:

...x...x
x..x..x.
.x.x.x..
..xxx...
xxx@xxxx
..xxx...
.x.x.x..
x..x..x.

The output may consist of any three distinct characters.

Examples and Test Cases

Input: (1/2)
Output:
.........
.........
..X.X....
.X...X...
...@.....
.X...X...
..X.X....
.........

Input: 2*
Output:
.........
.........
.X.X.X...
.........
.X.@.X...
.........
.X.X.X...
.........

Input: 2+.1+    (compare to the knight, above)
Output:
.........
...X.....
..X.X....
.X.X.X...
X.X@X.X..
.X.X.X...
..X.X....
...X.....

Input: @1<X>,2-3>=
Output:
...X....
...X....
...X....
..X.X...
XX.@.XX.
...X....
........
........

Input: 1+,2X&
Output:
.......X
........
.X...X..
...X....
..X@X...
...X....
.X...X..
........

This is - shortest code for each language in bytes wins.

Notes/Questions:

I have also considered having the location of the piece be arbitrary, given by another input. Is this a good idea? Does it make the challenge more interesting, or just more complicated without much benefit?

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ Have it variable. It makes it more interesting. \$\endgroup\$ – wizzwizz4 Dec 16 '17 at 19:46
2
\$\begingroup\$

Not-So-Simple Simplex

(Note: should I name it Complex Simplex?)

A simplex is an n-dimensional analog of a triangle. Thus, a 3-dimensional simplex is a tetrahedron. We want to find the number of points with integer coordinates (lattice points) strictly on the interior of this simplex. A point that lies on the boundary is not considered to be in the interior. For example, in a 2-dimensional simplex, any point on its perimeter is not an interior point. In a 3-dimensional simplex, any point on its surface area is not an interior point. In an n-dimensional simplex, any point on its surface n-1-volume is not an interior point.

You are given n + 1 points, each with n integral coordinates. You must output the number of integer points strictly in the interior of this simplex. The simplex is guaranteed to be non-degenerate, that is, it has strictly positive n-volume. If I provide 4 points, for example, you can assume they do not all lie on the same plane.

Test cases:

(0,0), (6,1), (2,5) -> 12 (see picture)

enter image description here

(2,3),(5,2),(3,2) -> 0

More test cases coming when I actually write the program to solve this because drawing the picture of a 4-simplex is a nightmare..

| |
\$\endgroup\$
  • \$\begingroup\$ Winning criteria? \$\endgroup\$ – user202729 Dec 24 '17 at 6:27
  • \$\begingroup\$ Code golf, let me add that. \$\endgroup\$ – rigged Dec 24 '17 at 17:39
2
\$\begingroup\$

Megatanium trading

Your task is to build a javascript function to trade a fictional stock called Megatanium
You start with $1000 and 0 stock of Megatanium

Challenge

This is a challenge, all submissions should be written in

Your function should accept four variables as follows, obviously within your function you can name these whatever you like
- 1st variable represents the current value of 1 bar of Megatanium
- 2nd variable represents your current bank balance
- 3rd variable represents your current stock holding
- 4th variable represents the iteration number

Your function should return an integer representing the size of your desired trade
The return value should be negative if you wish to sell stock, positive if you wish to buy stock, 0 if you wish to neither buy or sell

For example;
If you wish to buy 10 bars of Megatanium at the current price you would return 10
If you wish to sell 5 bars of Megatanium at the current price you would return -5

I will call your function 1000 times. Stock price will always be an integer, chosen at random, with a minimum of 0 and a maximum of 256. Method of selecting the stock price is described in more detail below, it will NOT be an even distribution!

Your bot will be disqualified if it does any of the following at any point

  • Try to buy more stock than it can afford
  • Try to sell more stock than it holds
  • Try to write any value to any of the global variables
  • Fail to return a value
  • Return a value that is not an integer

Here is the code I will be running, the score output at the end will be your bot's score. It is calculated from your bank balance plus the value of your held stock at the latest value.

function go(bot) {
    bank = 1000;
    stock = 0;
    disqualified = 0;
    for (i=1; i<=1000; i++) {
        price = prices[i];
        trade = window[bot](price, bank, stock, i);
        if (trade !== parseInt(trade)) disqualified = "INVALID TRADE";
        bank = bank - (price * trade);
        stock = stock + trade;
        if (bank < 0) disqualified = "RUN OUT OF MONEY";
        if (stock < 0) disqualified = "TRIED TO SELL STOCK YOU DIDN'T OWN";
        if (disqualified) break;
    }
    if (disqualified) {
        console.log("Disqualified on iteration " + i + " REASON: " + disqualified);
    }
    else {
        score = bank + (stock * price);
        console.log(bot + " scores " + score);
    }
}

The function for generating a suitable distribution of random values is a slightly modified version of the function described here
Every bot will be given the same set of prices, but the set will not be generated until immediately before the bots are run.

function randn_bm() {
    var u = 0, v = 0;
    while(u === 0) u = Math.random();
    while(v === 0) v = Math.random();
    w = Math.floor(Math.sqrt( -2.0 * Math.log( u ) ) * Math.cos( 2.0 * Math.PI * v ) * 32) + 128;
    while (w < 0 || w > 256) w = randm_bm();
    return w;
}
prices = [];
for (i=1; i<=101; i++) {
    prices.push(randn_bm());
}

Completion

You may submit as many bots as you like, try to be inventive with your algorithms! You may use a global variable called data, this will be initially set to null and will always be available to your function.

Example bots

function buyBot(p,b,s,i) {
    /* Bot always buys as much as it can */
    return Math.floor(b / p);
}

function randomBot(p,b,s,i) {
    /* Bot buys and sells randomly */
    if (Math.random() > 0.5) {
        return Math.floor(Math.random() * (b / p));
    }
    else {
        return -Math.ceil(Math.random() * s);
    }
}

function smartBot(p,b,s,i) {
    /* Bot always buys at under 100 and sells at over 150 */
    if (p < 100) {
        return Math.floor(b / p);
    }
    else if (p > 150) {
        return -s;
    }
    else {
        return 0;
    }
}

function bankruptBot(p,b,s,i) {
    /* Bot always sells at under 100 and buys at over 150 */
    if (p > 150) {
        return Math.floor(b / p);
    }
    else if (p < 100) {
        return -s;
    }
    else {
        return 0;
    }
}

function alternateBot(p,b,s,i) {
    /* Bot buys and sells alternately */
    if (data == 1) {
        data = 0;
        return Math.floor(Math.random() * (b / p));
    }
    else {
        data = 1;
        return -Math.ceil(Math.random() * s);
    }
}

Winning conditions

All bots will be run on locally by me approximately 1 week after the question is posted (date will be decided when question is posted, no point setting a date in sandbox)
Winner will quite simply be the bot that has the highest final score after the last iteration, as calculated by the function provided above. The array of prices used will be published after a winner has been crowned.
There are no set conditions on the speed of your function, but please be fair and try to avoid anything that will take more than a couple of minutes to execute

| |
\$\endgroup\$
1
18 19
20
21 22
100

You must log in to answer this question.

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