560
\$\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\$
0

4327 Answers 4327

1
58 59
60
61 62
145
1
\$\begingroup\$

Insertion sort counter

Calculate the number of moves necessary to do an insertion sort of an input vector containing positive integers.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

You must count the number of times a number is moved from its original position. For instance, the vector [1,2,3,4] requires no moves, as it's already sorted, while the vector [1,3,4,2] requires one move, since the last 2 must be moved two places to the left.

Example:

Input: 
[6, 5, 3, 1, 8, 7, 2, 4]
Sorting:
0: [6, 5, 3, 1, 8, 7, 2, 4]
1: [5, 6, 3, 1, 8, 7, 2, 4]
2: [3, 5, 6, 1, 8, 7, 2, 4]
3: [1, 3, 5, 6, 8, 7, 2, 4]
4: [1, 3, 5, 6, 7, 8, 2, 4]
5: [1, 2, 3, 5, 6, 7, 8, 4]
6: [1, 2, 3, 4, 5, 6, 7, 8]
Output: 6

Test cases:

To be added!

\$\endgroup\$
8
  • \$\begingroup\$ You should describe what an insertion sort is, for those who don't know. \$\endgroup\$
    – Okx
    Oct 24, 2017 at 9:13
  • \$\begingroup\$ Will do :) Thanks. \$\endgroup\$ Oct 24, 2017 at 9:13
  • \$\begingroup\$ As defined, the answer is always len(input). I've no idea what the example is supposed to show (or how it's counting). \$\endgroup\$ Oct 25, 2017 at 7:27
  • \$\begingroup\$ @PeterTaylor The number of insertions (maybe I should call it moves, or something else?) necessary for the array [1, 2, 3, 4] is zero. The number of moves for the array [1, 3, 4, 2] is one, since the only number that must be moved when using the insertion sort algorithm is the last 2, that must be moved two steps to the left, resulting in a sorted array. Placing a number back in its original position doesn't count as an insertion/move. Does that make sense? \$\endgroup\$ Oct 25, 2017 at 7:58
  • \$\begingroup\$ So "Count the number of array elements a[i] which are not the greatest element in a[:i+1]"? \$\endgroup\$ Oct 25, 2017 at 8:25
  • \$\begingroup\$ I guess that's another way to put it, yes... \$\endgroup\$ Oct 25, 2017 at 8:53
  • 1
    \$\begingroup\$ Maybe you could have it count the number of swaps assuming that you can only move a number by swapping it with one of its neighbors (and many implementations of insertion sort actually do this, especially those operating on arrays). For example, the number of moves for [1,3,4,2] would be 2, because the number 2 must be shifted twice to the left. \$\endgroup\$
    – Leo
    Oct 26, 2017 at 4:37
  • \$\begingroup\$ That's actually a good idea. Thanks! :) I'll probably change it when I get the time. :) \$\endgroup\$ Oct 26, 2017 at 6:04
1
\$\begingroup\$

Tear Down that Wall

Related (dupe?)

  • This is my first time submitting a challenge.
  • Suggestions and constructive criticism are always welcome.

Cops:

As the cop, your task is to create a code that outputs this ASCII wall:

___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__

However, by deleting some part(s) of the code, it must also output a broken wall:

___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__

Rules:

  1. Your code must terminate in a reasonable amount of time as long as it's correct. That means that the whole code and the correctly broken code must output the wall (broken or not) within 60 (too much or too little time? sugestions?) seconds. That doesn't apply if the code is incorrectly broken by the robber.
  2. The broken wall needs to be output(ted? English is hard) without addition of code.
  3. You may obfuscate the code as much as you see fit. (does hashing/encrypting count as obfuscating? if so, should it be allowed?)
  4. You must state what language you used in your answer.
  5. Your wall will be safe if, after 1 week, it hasn't been broken. You must also reveal the answer. Your wall will not be safe until you have revealed the answer.
  6. The outputs must match the exact ASCII walls provided. Leading/trailing newlines are allowed as long as the output matches the one provided. The walls consist of 13 lines and 38 columns of the characters | and _. The broken section of the wall is a block of 20 whitespace characters per line, beginning at the fourth line. The "padding" is of 9 characters (| or _) to either side of the whitespace block.
  7. Preferably, include a link to an online interpreter for your chosen language.

(any other rules suggestions?)

Robbers:

As the robber, your task is to, well, break the wall!

Rules:

  1. You may not add any code to the answer, only delete.
  2. The code is considered broken if and only if it outputs the entire broken wall.
  3. The broken code must be a valid submission in the same language as the original code.
  4. Please include in your answer a link to the answer you cracked and which part(s) of the code you modified.

Sandbox:

  • Suggestions?
\$\endgroup\$
3
1
\$\begingroup\$

Does the Riemann hypothesis hold?

I would like to earn a million dollars, and the hardest way to do it is apparently solving one of the Millenium problems, so let's focus on one: the Riemann hypothesis.

Now, how could I possibly ever solve it? By writing a computer program, of course! However, I am lazy, so I would rather have you do the work for me by making the program as short as possible (to minimize the number of key strokes required for me to verify your results)

The challenge

Your goal is to write a program in a language of your choice which would decide the Riemann hypothesis. More precisely, you should write a program which terminates iff the Riemann hypothesis fails.

Restrictions

  • The program has to work when running with empty input [Sandbox note: perhaps allow input but add it to byte count?]
  • Standard loopholes are forbidden.
  • Your program must provably terminate iff RH is false. For example, submitting two programs, one trivially terminating, one trivially not terminating, and claiming one of them works, is not allowed, since neither of the programs provably works.
  • You must give a proof of equivalence of your program's termination with RH failing, with references to other work allowed. I give myself the right to decide whether the work referenced is valid or not, to exclude the many proofs and disproofs of RH.
  • If the Riemann hypothesis doesn't hold, your program can throw an error, or simply exit, as long as the program cannot continue beyond that.
  • You may assume you have unlimited memory and time, and also that your number types can hold real numbers of arbitrary size to arbitrary precision.
  • This is , so the shortest code in bytes wins!

Sandbox comment

To address the comments below, let me clarify why this challenge is most definitely solvable. Note that the problem is not of the sort "give a counterexample to RH" (if it did, then it would fall under this discussion and I completely agree it would not be a good challenge). Instead, it asks for a program whose termination depends on RH, and then one can give valid solutions regardless of the fact that RH is not solved yet.

To give an analogy (following Deedlit's example), suppose we have replaced RH with Goldbach's conjecture. This conjecture surely is unresolved, but one can give a valid solution to the challenge, for example by following this pseudocode:

n = 4
while true:
 found = false
 for k from 1 to n-1:
  if k is prime and n-k is prime:
   found = true
   break
 if found == false:
  break
 else:
  n = n+2
return 0

If Goldbach's conjecture is false, this program will eventually terminate by returning 0 (namely, when it finds the first counterexample). Otherwise, it will stay in the while loop forever. Hence it would be a valid solution.

My challenge as it stands can be solved in a similar manner, perhaps using

one of the many known equivalents of RH.

\$\endgroup\$
19
  • \$\begingroup\$ codegolf.meta.stackexchange.com/q/11033/45941 \$\endgroup\$
    – user45941
    Oct 27, 2017 at 19:47
  • 1
    \$\begingroup\$ @Mego My proposed challenge doesn't fall under that discussion. It is not an open problem whether a solution for that problem is possible. \$\endgroup\$
    – Wojowu
    Oct 27, 2017 at 19:51
  • \$\begingroup\$ Relying on open problems for challenges is not a good idea. Either it will be impossible to answer because the problem isn't solved, or answers will be trivial copy jobs of the proof once the problem is solved. This challenge relies on both an open problem (Riemann hypothesis) and an unsolvable problem (halting problem). \$\endgroup\$
    – user45941
    Oct 27, 2017 at 20:42
  • 1
    \$\begingroup\$ @Mego The way I have phrased my problem makes it possible, but not trivial, once the Riemann hypothesis is unsolved. True, the problem trivializes once we get a (dis)proof of RH, but until then I don't see an issue with this problem. Also, I don't see how halting problem is in any way relevant here. \$\endgroup\$
    – Wojowu
    Oct 27, 2017 at 20:58
  • \$\begingroup\$ You don't see how the halting problem is relevant in a challenge for writing problems that halt iff some unsolved problem in mathematics is true? \$\endgroup\$
    – user45941
    Oct 27, 2017 at 20:59
  • 1
    \$\begingroup\$ @Mego Let me rephrase - I don't see how its unsolvability impacts the challenge in any way. \$\endgroup\$
    – Wojowu
    Oct 27, 2017 at 21:01
  • 3
    \$\begingroup\$ @Mego As an example, it is straightforward to write a program that halts if and only if the Goldbach conjecture is false. Simply test out even numbers one at a time until you find one that is not the sum of two prime numbers. The unsolvability of the halting problem doesn't have any bearing on this, since we aren't relying on an algorithm that determines the halting behavior of all programs. A program that halts precisely when the Riemann Hypothesis is true could be done similarly. \$\endgroup\$
    – Deedlit
    Oct 27, 2017 at 22:01
  • \$\begingroup\$ @Deedlit Can one also show that it is possible to write a program that halts iff Goldbach's conjecture is true? \$\endgroup\$ Oct 27, 2017 at 22:31
  • \$\begingroup\$ @JonathanFrech I believe that's an open problem. However, thanks to your comment I've realized I have mixed things up - my challenge should've been about RH being false, not true (so just like in Deedlit's example with Goldbach). Sorry if any confusion was caused. \$\endgroup\$
    – Wojowu
    Oct 27, 2017 at 22:43
  • \$\begingroup\$ @Wojowu Well, that seems solvable then. Would one, however, not simply loop through all complex numbers (as one has a lot of computational power), implement the zeta function (again, infinite computational power) and halt if they find a counterexample to the hypothesis? \$\endgroup\$ Oct 27, 2017 at 22:49
  • \$\begingroup\$ @JonathanFrech It needs to be quite a bit more than that, because there are uncountably many complex numbers, so you can't loop over them all even with unbounded computing power. I believe you can do it by evaluating a contour integral around rectangles in the complex plane and looping over these rectangles. And it gets annoying around the critical line. It's definitely more complicated than just implementing the zeta function, though. \$\endgroup\$
    – Chris
    Oct 28, 2017 at 1:58
  • \$\begingroup\$ @Chris Could one not loop through all possible sums of all rationals to approximate the reals, argue that every real is computable by an infinite sum of rationals, do that twice to gain a program which theoretically looks at every complex number, implement the zeta function and check if the hypothesis holds? \$\endgroup\$ Oct 28, 2017 at 12:02
  • \$\begingroup\$ @JonathanFrech It's not possible to look at all possible infinite sums of rational numbers. Some (in fact, most) are uncomputable, and either way there are just too many real/complex numbers. Try to implement your algorithm in a real language like C, you will see that this simply doesn't go through. \$\endgroup\$
    – Wojowu
    Oct 28, 2017 at 12:06
  • 2
    \$\begingroup\$ @JonathanFrech It is not possible to cycle through all possible complex numbers, but there are other ways which would let one verify the Riemann hypothesis. \$\endgroup\$
    – Wojowu
    Oct 28, 2017 at 12:17
  • 1
    \$\begingroup\$ @Chris err, yes, that's what I meant. \$\endgroup\$
    – Wojowu
    Oct 28, 2017 at 20:40
1
\$\begingroup\$

Square-free Rock-Paper-Scissors tournament

On the day of the Codegolf Rock-Paper-Scissors tournament you hear through the grapevine that everybody else is going to play a fix square-free sequence (a sequence made of the letters R, P, S is square-free if it does not contain a subsequence that repeats twice. See Don't repeat yourself in Rock-Paper-Scissors for details.)

Task

Write a program that for a game of N rounds, in each round n

  1. prints one of R, P, S - its own nth hand (using all information gained so far)
  2. receives an input of either R, P, S - the nth letter of the opponent's sequence

Rules

  • Rock beats scissors, scissors beats paper, paper beats rock.

  • The "opponents" are all the square-free sequences of the given length.

  • Your program may read the opponents moves at once and print its own moves - as long as it is functionally equivalent to a program reading the moves in the order specified in section "task".

  • The program does not carry a state between playing against different opponents.

  • Each entry should include a scoring script computing the score of the candidate against all square-free sequences of length N.

Scoring

I am posting this to get some input about interesting scoring methods and a good choice of N.

Programs should score high if they win against a large fraction of square free sequences in an economic way. A possible criterium of "winning" against a single sequence is winning more hands against an opponent than losing. A possible criterium of scoring high is number of games won divided by the root of bytes.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'd say 16 could be a good choice for N, this would give 798 different opponents, which are still a manageable amount, and each game would probably be long enough to make the square-free analisys matter \$\endgroup\$
    – Leo
    Oct 31, 2017 at 3:39
  • \$\begingroup\$ To win with a small margin it is enough to exploit that the sequence does not repeat. I think we need to put the winning margin into the score or put a threshold. \$\endgroup\$
    – mschauer
    Oct 31, 2017 at 7:58
  • \$\begingroup\$ Maybe (rounds won - rounds lost)/bytes^2 , where rounds are counted from all the matches together \$\endgroup\$
    – Leo
    Oct 31, 2017 at 8:50
1
\$\begingroup\$

Can You Catch the Robber?

This is not a cops and robbers type challenge, but a code-golf challenge based on the PBS Infinite Series video Cops and Robbers Theorem.

Challenge

You will be given an undirected and connected graph. You may also assume the graph contains no self-loops; that is, the graph will not contain a vertex with an edge connecting to itself. You must determine if the graph is cop-win. That means that if a cop and robber start at any vertex, the cop will eventually land on the same vertex as the robber, with the cop and robber taking turns traversing one edge at a time, starting with the cop. Both the cop and the robber are playing optimally and have the option to not move on their turn.

If you haven't watched the video, let me explain how to simplify the problem. First, let's start with a definition. A pitfall is any vertex v whose neighbors are all a distance of 0 or 1 from a common vertex w, where v is not equal to w. To determine if a graph is cop-win, you must repeatedly remove pitfalls and the edges that connect to it until the graph is reduced to a single vertex or there are no more pitfalls to remove. If the graph can be reduced to a single vertex in this way, it is cop-win. A couple visual examples follow.

Example 1

>o---o---o
  \ / \ /
   o---o
    \ /
     o

  o---o<
 / \ /
o---o
 \ /
  o

 >o
 / \
o---o
 \ /
  o

>o---o
  \ /
   o

 >o
 /
o

o

Result: Cop-win

Example 2

  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
 /     \
o       o
 \     /
  o---o

Result: Not cop-win

Examples

Input: [[2,3],[2,4],[0,1,3,4,6],[0,2,5,6,8],[1,2,6,7,9],[3,8],[2,3,4,8,9,10],[4,9],[3,5,6,10],[4,6,7,10,11],[6,8,9,11],[9,10]]
Output: Truthy

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

Input: [[1,2],[0,3],[0,3],[1,2]]
Output: Falsy

Input: [[1,2,3],[0,2,3],[0,1,3],[0,1,2]]
Output: Truthy

Rules

You may take input as an adjacency list, adjacency matrix, or list of edges, whose vertices may be 0-indexed or 1-indexed. Your output must be a truthy or falsy value. This is , so the least number of bytes in each language wins.

Notes

This is my first post; I could certainly benefit from some help in formulating and polishing my challenge. If anyone believes my language was ambiguous or contradictory to what was said in the video, please help me clarify.

\$\endgroup\$
7
  • \$\begingroup\$ What is the input here? It looks a list of each vertex's neighbors, but could you clarify? \$\endgroup\$
    – KSmarts
    Oct 3, 2017 at 15:16
  • \$\begingroup\$ Yes that's what I was going for, an adjacency list. A map of each vertex to a list of its neighbors. \$\endgroup\$
    – kamoroso94
    Oct 3, 2017 at 16:34
  • 2
    \$\begingroup\$ This looks like a good question: meaty enough that there's something to golf, but simple enough not to scare everyone away. What I would suggest is flexibility in the input: allow people to choose whether to take input as adjacency matrix, adjacency list in the format you've used for the test cases, or list of edges. Also, allow people to use 1-indexed vertices rather than 0-indexed if they prefer. \$\endgroup\$ Oct 10, 2017 at 8:18
  • \$\begingroup\$ I definitely agree with your suggestion of input leniency. I'll update the challenge. \$\endgroup\$
    – kamoroso94
    Oct 12, 2017 at 8:57
  • 1
    \$\begingroup\$ I'd suggest explaining what a cop-win graph is in full, including the start positions and that both players play an optimal strategy. A link to a non-video explanation would also be good for anyone who can't or doesn't want to watch a video. \$\endgroup\$
    – xnor
    Oct 12, 2017 at 21:06
  • \$\begingroup\$ Thank you for the feedback, @xnor. I've worked it into the challenge. I feel it's an improvement. I think that the visual examples take up too much vertical space, so I'm not sure if I should include them or not. \$\endgroup\$
    – kamoroso94
    Oct 31, 2017 at 2:17
  • \$\begingroup\$ IIRC it shouldn't be "start at any vertex", but the selection of the start position is part of the game, also under condition of optimal play, with the cop selecting their position first. \$\endgroup\$ Oct 31, 2017 at 13:00
1
\$\begingroup\$

Polynomial Partition

META: Right now I'm wondering whether it would be a more interesting challenge to have two imput lists, and the program just needs to find a polynomial that separates the two lists (i.e. no connected component can contain points of both classes. Or altnernatively f(x,y)>0 for all (x,y) in list A, and f(x,y)<0 for all (x,y) in list B.

Given a finite list of at at least two points in the plane ℝ² (all points in the list are unique), your program should find a polynomial f in ℝ[x,y] whose zero locus Z(f) := {(x,y) ∊ ℝ² | f(x,y) = 0} partitions the plane such that each of the connected components of ℝ²\Z(f) contains at most one point of the input list. The goal is finding such an f of a low degree. (It does not have to be optimal.) Note that no point of the input list may be contained in Z(f).

Scoring

The score for each test cases is the degree of the polynomial that your algorithm produces. The total score is the product of the scores of the testcases.

Examples

The points {(0,0),(0,2)} can be separated by f(x,y) = y - 1 (degree 1) or f(x,y) = x² + y² - 1 (degree 2) or f(x,y) = x³ + 1 - y(degree 3) or (infinitely) many more.

The points {(1,1),(-1,1),(-1,-1),(1,-1)} can be separated by f(x,y) = xy (degree 2).

Test Battery

to be included...

\$\endgroup\$
2
  • 1
    \$\begingroup\$ (1) I presume that the words "a different" are missing from "each of the inputs is in ^one of the connected components". (2) Is the optimal solution not going to be one of the easiest approaches? \$\endgroup\$ Nov 3, 2017 at 11:44
  • \$\begingroup\$ Thanks for the feedback, I rewrote (1), regarding (2): One very easy not optimal solution would be making a a small enough circle around every point, so I guess it depends. \$\endgroup\$
    – flawr
    Nov 3, 2017 at 14:43
1
\$\begingroup\$

Palindromic Collapse

Given a string s, traverse from left-to-right, finding the first prefix that is a palindrome. When you encounter the first prefix palindrome, remove the end-half of the palindrome. Insert it back into the original string, then restart again from the left side of the new word. Return the final result when no prefixes are palindromes.

Take for example "babble":

  • First check would be [ba]bble, which is not a palindrome, move on.
  • Second check would be [bab]ble, which is a palindrome (bab).
    1. Compress the palindrome to the first "half", [bab] becomes [ba].
    2. Reattach this in place of the original palindrome, resulting in [ba]ble
  • Next we repeat, finding [bab]le again, and resulting in [ba]le after steps 1 and 2.
  • We then iterate through the full word again, finding no palindromes, returning bale.

More Examples (worked out)

moom

[mo]om (not a palindrome)
[moo]m (nont a palindrome)
[moom] (palindrome) -> [mo]
[mo]   (not a palindrome, done).

Final returned result: mo


abalbalba

[ab]albalba (not a palindrome)
[aba]lbalba (palindrome) -> [ab]lbalba
[ab]lbalba  (not a palindrome)
[abl]balba  (not a palindrome)
[ablb]alba  (not a palindrome)
[ablba]lba  (palindrome) -> [abl]lba
[ab]llba    (not a palindrome)
[abl]lba    (not a palindrome)
[abll]ba    (not a palindrome)
[abllb]a    (not a palindrome)
[abllba]    (palindrome) -> [abl]
[ab]l       (not a palindrome)
[abl]       (not a palindrome, done)

Final returned result: abl


More 1-1 Examples

amanaplanacanalpanama -> amnaplanacanalpanama
1232132121            -> 123
1232132145            -> 12345
01001000123210        -> 01123210
01000000000000000001  -> 011
010101                -> 011
abbabababaa           -> ab
hellollehworld        -> helloworld
world                 -> world
<empty string>        -> <empty string>
\$\endgroup\$
2
  • \$\begingroup\$ You like palindrome a lot, don't you? \$\endgroup\$
    – Mr. Xcoder
    Nov 7, 2017 at 20:00
  • \$\begingroup\$ @Mr.Xcoder in all fairness it looks like Oliver Ni likes them more. \$\endgroup\$ Nov 7, 2017 at 22:06
1
\$\begingroup\$

Validate a StarCraft II Build Order

Explanation

You must decide whether the input represents a valid StarCraft II Build Order. Here is how you will decide:

  1. Start with the first word (it will be the race, Zerg, Protoss, or Terran)
  2. Set the list of valid units to just the ones from that race (explained later)
  3. Loop through the input (split by space)
    1. Check if the unit is in the list of valid items for the listed race
      • Otherwise, output Invalid item + the listed item's name
    2. Check that the player has enough supply to sustain that unit (if it's a unit) (explained later)
    3. Check that the player has the prerequisites for that item

Units and Structures

(will be listed in real question)

Example:

Terran:

  • CommandCenter 0 supply, requires SCV gives +15 supply
  • OrbitalCommand 0 supply, requires CommandCenter (consumes)

Zerg:

  • Hatchery -1 supply, requires Drone (consumes) gives +6 supply
  • Drone 1 supply, requires Hatchery
  • SpawningPool -1 supply, requires Hatchery, Drone (consumes)

Protoss:

  • Nexus 0 supply, requires Probe gives +15 supply

StarCraft II Mechanics

At the beginning of the game, the player starts with a town hall (Nexus, CommandCenter, or Hatchery + Overlord) and 12 workers (Probe, SCV, or Drone).

Supply is the maximum number of units one can have. Supply Depots, Pylons, and Overlords give more supply.

The sum of the supply of all produced units can never exceed the current supply value (we ignore Zerg hacks).

The Supply cannot exceed 200.

Input

You will receive an input in any valid way in this format:

Race <item> <item> .....

There will be at most 99 items, and they will be at most 30 chars long.

The race will be one of Zerg, Protoss, or Terran.

\$\endgroup\$
1
\$\begingroup\$

Lines per file

Can't believe it was not questioned yet.

I want the shortest script you can supply to take on all files on a directory and output a list in the format

file number_of_lines

Every possibility should be accounted as a valid line terminator:

- <CR>
- <LF>
- <CR><LF>
- <LF><CR>

No winner, it is a per language basis. Still thinking if I should give some bonus for sorting by line count.

\$\endgroup\$
3
  • \$\begingroup\$ Duplicate. Not the same but pretty much the same idea, would definitely get closed for dupeness. \$\endgroup\$
    – Riker
    Nov 14, 2017 at 18:58
  • \$\begingroup\$ @Riker: Counting lines requires some more effort than the file's byte size! I had even posted an answer on that question! \$\endgroup\$
    – sergiol
    Nov 14, 2017 at 21:18
  • 1
    \$\begingroup\$ It's literally just wc -l to count lines.. I'm not sure about most of the others, but I know at least my bash can be trivially modified to count lines. \$\endgroup\$
    – Riker
    Nov 14, 2017 at 21:33
1
\$\begingroup\$

Prune my tree

Given a well-formed ASCII art tree and the name of a node, print or return a new, well-formed tree with that node and any children removed.

†Contains non-ASCII characters.

Example

Given this input tree:

A
├ B
├ C
│ └ D
└ E

...and the node name E, the following should be returned:

A
├ B
└ C
  └ D

Well-formed trees

Rather than an exhaustive spec, I'll define well-formedness by example:

A
├ B
├ C
├ D
│ ├ E
│ └ F
├ G
│ └ H
│   ├ I
│   │ ├ J
│   │ └ K
│   └ L
└ M
  ├ N
  │ └ O
  │   └ P
  ├ Q
  └ R

The above is the only valid way to represent this tree (rules above re: trailing spaces and newline apply here and henceforth). Note that:

  1. The tree is rendered with some strict subset of the characters , , , AZ, space, and newline.
  2. The tree has one root node (in this example A) with no characters to its left or right.
  3. Each line has exactly one node.
  4. Each and is followed by a single space (required) and node name.

Rules

  • Standard loopholes are forbidden.
  • This is an challenge; input and output must be a string or array of lines or equivalent, per standard rules.
  • Trailing spaces and/or a single trailing newline are allowed in both input and output.
  • You may use any character encoding, as long your solution prints or returns characters equivalent to , , and . (ASCII characters like +, | (pipe) and L (capital "l") are not equivalent.)

    See also "Freebies" under "Scoring" below.

Input

  • The input tree will have at least one node.
  • The given named node may or may not exist in the tree. If it does not exist, the original tree should be returned.
  • Each node name will be a single character between A and Z inclusive. Node names will be unique and there will be no more than 26 nodes.
  • Node names are not guaranteed to be contiguous nor in any particular order, e.g. the following is possible input:

    Q
    └ D
    

Output

  • The output tree may have zero nodes.
  • The order of the remaining nodes in the output tree must be the same as the input tree.

Scoring

This is . The shortest solution in bytes wins.

🌟Freebies🌟: If the literal characters , , or appear in your source code, you may count them as one byte each, per occurrence.

Test cases

I'll reuse a few trees for multiple test cases.

  1. Input tree:

    A
    
    • Output if A removed:

      
      
    • Output if B removed (B doesn't exist):

      A
      
  2. Input tree:

    A
    ├ B
    ├ C
    │ └ D
    └ E
    
    • Output if C removed:

      A
      ├ B
      └ E
      
    • Output if D removed:

      A
      ├ B
      ├ C
      └ E
      
    • Output if E removed:

      A
      ├ B
      └ C
        └ D
      
  3. Input tree:

    A
    ├ B
    ├ C
    ├ D
    │ ├ E
    │ └ F
    ├ G
    │ └ H
    │   ├ I
    │   │ ├ J
    │   │ └ K
    │   └ L
    └ M
      ├ N
      │ └ O
      │   └ P
      ├ Q
      └ R
    
    • Output if H removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      ├ G
      └ M
        ├ N
        │ └ O
        │   └ P
        ├ Q
        └ R
      
    • Output if L removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      ├ G
      │ └ H
      │   └ I
      │     ├ J
      │     └ K
      └ M
        ├ N
        │ └ O
        │   └ P
        ├ Q
        └ R
      
    • Output if M removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      └ G
        └ H
          ├ I
          │ ├ J
          │ └ K
          └ L
      

Questions for sandbox:

  1. Enough/too many/missing test cases?
  2. Enough/too many/missing details re: input/output?
\$\endgroup\$
4
  • \$\begingroup\$ I would just make this an (actual) ASCII-art challenge. Up to you but meh \$\endgroup\$
    – hyper-neutrino Mod
    Nov 13, 2017 at 19:24
  • \$\begingroup\$ Given the proximity to Christmas, you could go for "trim the tree" as the title. \$\endgroup\$
    – Nissa
    Nov 13, 2017 at 21:47
  • \$\begingroup\$ I think you should show the larger test case(s) with A removed. I know/guess it will be an empty output, but still, it's a corner case that will benefit from being properly shown. \$\endgroup\$ Nov 15, 2017 at 12:24
  • \$\begingroup\$ I like the idea, but I too would prefer ASCII-only. Non-ascii adds a bunch of bytes without adding anything to the challenge itself. \$\endgroup\$ Nov 15, 2017 at 12:29
1
\$\begingroup\$

Smallest Proth Prime Power

A Proth Prime is a prime number of the form (k*2^n)+1.

The Challenge

Given a positive integer k, return the smallest non-negative integer n such that (k*2^n)+1 is a prime.

This is code-golf, so smallest answer in bytes will win!

OEIS link for this sequence

OEIS link for sequence shifted by 1, with alternative calculation method

Test cases:

Input Output
1     0
2     0
3     1
4     0
5     1
6     0
7     2
8     1
9     1
10    0
11    1
12    0
13    2
14    1
15    1
16    0
17    3
18    0
19    6
20    1
46    0
47    583
48    1

TODO:

  • Rework preamble
  • More/better test cases?
\$\endgroup\$
1
\$\begingroup\$

Packing Density of Polyline Defined Shapes

So... I was making bacon this morning and I couldn't fit all of my bacon into my pan. However I oriented the strips, there was always one or two pieces that didn't fit. Culinary endeavors aside, here's my challenge:

Input:

pan and bacon

Each of these inputs is a list of (X,Y) coordinates that define a closed shape. The very first index and the very last index are different, but the shape is closed. It not guaranteed that the shape is convex, but it is guaranteed that the path doesn't cross itself. Further, for simplicity, you may expect all the (x,y) coordinates to be integers.

Your program must find the most occurences of bacon that can fit into the pan, allowing rotation and flipping.

Output:

An integer that represents how much bacon can fit in the pan.

Scoring and rules:

For proper cooking:

  • A bacon may touch another bacon or the edge of the pan.
  • bacon may not overlap, nor may it go off the pan.
  • The first index of both pan and bacon is always (0,0).
  • If there is a tie in number of bytes, the user whose code is formatted to look like ASCII bacon wins.
  • If two users tie and both have ascii bacon, upvotes wins. Standard rules apply. This is code golf, so the standard rules apply.

Sample input and output:

Test Case 1:

Bacon directly overlaps the pan, and is the same size.

pan: [(0,0),(0,1),(1,1),(1,0)]
bacon: [(0,0),(0,1),(1,1),(1,0)]
Output: 1

Test Case 2:

When bacon is bigger than pan

pan: [(0,0),(0,1),(1,1),(1,0)]
bacon: [(0,0),(0,2),(2,2),(2,0)]
Output: either 0 or an error.

Test Case 3:

What happens when bacon crosses itself?

pan: [(0,0),(0,1),(1,1),(1,0)]
bacon:[(0,0),(1,1),(0,1),(1,0)]
Output: just error here. Any way you feel like. If you manage to report an http 418 error, you get bonus points, redeemable for nothing.

Test Case 4:

What happens if the bacon doesn't exactly overlap the pan?

pan: [(0,0),(0,3),(5,3),(3,0)]
bacon: [(0,0),(0,2),(2,2),(2,0)]
Output: 2

\$\endgroup\$
5
  • 1
    \$\begingroup\$ This looks like a tough question, but I like it. 1.) Are the coordinates integers or can they be floats? 2.) Is the shape guaranteed to be convex and contain more than two coordinates? 3.) Because this is a code golf challenge, it's unlikely anyone will go for the second output, so you should probably stick with just one of the two output methods. 4.) Example inputs and outputs would be great. \$\endgroup\$
    – Laikoni
    Nov 16, 2017 at 21:15
  • \$\begingroup\$ Having arbitrary polygons make this tough, even just to figure out if one shape fits inside another. I think you'll do well to have extensive test cases that probe at the possibilities and defy heuristics. \$\endgroup\$
    – xnor
    Nov 16, 2017 at 21:42
  • \$\begingroup\$ I've added quite a few test cases using minimal pans and bacon. @xnor, what do you mean by 'defy heuristics'? \$\endgroup\$ Nov 16, 2017 at 21:57
  • \$\begingroup\$ @JakobLovern Like, for example, making it so that code that just outputs the ratio of the areas doesn't happen to pass all test cases. Other examples could be making sure the code allows bacon to be rotated by non-multiples of 90 degrees, doesn't just try to do some greedy fill from one corner, considers reflecting the bacon, etc. The idea is that someone whose code meets all the tail cases should be reasonably certain it meets the problem conditions. \$\endgroup\$
    – xnor
    Nov 16, 2017 at 22:36
  • 1
    \$\begingroup\$ @JakobLovern My experience has been that writing the code to do the task has been very helpful to think of edge cases and to generate test cases. You can then post it as (ungolfed) reference code, which is often appreciated by solvers. \$\endgroup\$
    – xnor
    Nov 16, 2017 at 22:43
1
\$\begingroup\$

Moore-Penrose inverse

In linear algebra the pseudo-inverse of a matrix is a generalization of the inverse of a matrix which doesn't necessarily exist. One definition of a pseudo-inverse is called the Moore-Penrose inverse which shall be denoted by A⁺ in the following. Further let Aᵀ denote the transpose of the matrix A.

Definition

The Moore-Penrose inverse of the matrix A is defined for all matrices A in a way such that it satisfies the following four properties:

  • AA⁺A = A
  • A⁺AA⁺ = A⁺
  • (AA⁺)ᵀ = AA⁺
  • (A⁺A)ᵀ = A⁺A

Task

Your task in this challenge is, given a matrix real A (non-zero and non-empty) to compute its pseudo-inverse as defined above.

  • You're allowed to receive input as a single list, array, list of lists etc.
  • The input is a single non-zero, non-empty matrix with real entries
  • The input matrix is not necessarily square
  • Your program/function either returns the pseudo-inverse or prints it to STDOUT
  • You don't need to handle floating point inaccuracies
  • The behavior on invalid input (eg. []) is left undefined

Examples

Here are some possible examples (note the different (in)accuracies):

[4] -> [0.25]
[1 1; 1 0] -> [0 1; 1 -1]
[12 4 9; -9 1 3; -6 6 15] -> [0.0467129 -0.0342457 -0.0217785; 0.0115298 0.0022497 0.0160292; 0.0251844 0.0076240 0.0404324]
[0 1 0; 0 0 1; 0 0 0; 2 0 0] -> [0 0 0 0.5; 1 0 0 0; 0 1 0 0]
[1 1 2 3] -> [0.0667; 0.0667; 0.1333; 0.2]
[0; 0; 1] -> [0 0 1]
[1 0 0 0 0; 2 0 0 0 0] -> [0.2 0.4; 0 0; 0 0; 0 0; 0 0]

Sandbox

  • Should I ban built-ins (looking at Octave/Matlab, Mathematica etc.)?
  • Is the part with floating-point inaccuracies formal/objective enough?
  • Are more examples needed?

Tags: , , ,

\$\endgroup\$
1
  • \$\begingroup\$ Having no challenge for computing a SVD, maybe I should reduce this to only computing the SVD of a matrix since that would be the heart of this challenge anyway. What do you think? \$\endgroup\$ Nov 22, 2017 at 15:00
1
\$\begingroup\$

Squaring the circle

Background

This is a generalization of this question on puzzling.SE. Essentially, it asks you to generate a circular array of integers such that any two adjacent integers add to a perfect square, and that the integers are a permutation of those from 1 to 50. The original question gave you a part of the array, and asked you to solve it. I wish to generalize this problem.

Problem Description

Given an integer n, generate a circular array of numbers from 1 to n such that any two adjacent integers sum to a perfect square, without repeats of any number.

Input

Input is limited to positive integers greater than or equal to two.

Output

If there is no possible array (as can be manually proven to be the case for n=4), then your function should gracefully handle the error and exit.

Otherwise, it should output a representation of that array for that n as a string of delimited integers, such that, if the string were concatenated into a long integer, it would be the minimum possible string. To illustrate:

1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Of these six representations, only 1 2 3 is in minimal form.

You may delimit your string in any consistent, parsable way you choose.

Example I/O

For n<32, there are no valid arrays (And I can prove it, if necessary.) The smallest n with a valid array is n=32, and it is structured:

=>01 08 28 21 04 32 17 19
15                       30
10                       06
26                       03
23                       13
02                       12
14                       24
22                       25
27                       11
  09 16 20 29 07 18 31 05

The output to n=32, would therefore be 1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

Example code

Because code is clearer than words, here's a (purposefully) very naive and inefficient routine for this in Python (2.7):

import math, itertools
def main(n):
  def test_if_a_given_list_is_a_ring(input_list):
    is_a_square = lambda value: math.sqrt(value).is_integer()
    output_flag = True
    for index in range(len(input_list)):
      if is_a_square(input_list[index]+input_list[index-1]):
        continue
      else:
        output_flag = False
      #end if
    #end for
    return output_flag
  #end test_if_a_given_list_is_correct
  def turn_it_into_a_string(input_list):
    temp_list = []
    for i in input_list:
      temp_list.append(str(i))
    #end for
    output_string = ''
    for i in temp_list:
      output_list += ' '+ i
    #end for
    return output_list[1:]
  #end turn_it_into_a_string  
 lowest = string(n)*n

 for perm in itertools.permutations(range(n,0,-1)):
    if test_if_a_given_list_is_correct(perm):
      flag = True
      for perm_character,lowest_character in zip(turn_it_into_a_string(perm),lowest):
        if int(lowest_character) < int(perm_character):
          flag = False
          break
        #end if
      #end for
      if flag:
        lowest = turn_it_into_a_string(perm)
      #end if
    #end if
  #end for
  return lowest
#end main

If you're gonna golf this code... I'd highly recommend optimizing it first.

Scoring

Programs will be scored based on: 1. Asymptotic complexity 2. Average runtime 3. Byte count 4. Runtime when the byte count is fed into the program as input

(I can't decide which of these scoring systems to use. Note that I've manually worked out that when n<=31, there are no arrays. At n=31, there is a valid double loop system, but no valid single loops.)

\$\endgroup\$
7
  • \$\begingroup\$ your example is not a valid ring, is it? I only see two perfect squares, 11+5=16 and 1+8=9 \$\endgroup\$
    – Luca H
    Dec 1, 2017 at 9:18
  • \$\begingroup\$ No, it isn't. As of ten minutes ago, I constructed (By hand) the ring for n=32, so I'll post that. \$\endgroup\$ Dec 1, 2017 at 18:56
  • \$\begingroup\$ (1) "ring" has a specific meaning (an algebraic structure with multiplication and addition subject to certain rules), which is distracting. How about changing it to circular array? (2) In my opinion, "generate a [circular array] of numbers from 1 to n" does not impose a restriction on the length of the array or on the impossibility of repeats. For me the clearest way to add the restrictions which I infer from the linked question would be to say that it's a permutation of the numbers from 1 to n. \$\endgroup\$ Dec 1, 2017 at 21:02
  • \$\begingroup\$ (3) "This is a two part question": I only see one part. If you intend a follow-up, maybe worth including it so that you can get opinions on whether it would be closed as a dupe of the first part. \$\endgroup\$ Dec 1, 2017 at 21:03
  • \$\begingroup\$ @PeterTaylor I was originally intending to ask the question twice, but score using different conditions. I expect that code which would minimize asymptotic complexity wouldn't look at all similar to code which minimizes size. I wanted to see the difference. You made a good point on the dupe problem, though, as the two questions are essentially similar to each other. \$\endgroup\$ Dec 1, 2017 at 21:44
  • \$\begingroup\$ So what's the scoring? If byte-count gets fed to the program no solutions that are < 31 bytes & if it's gonna be an average runtime based scoring you should choose large enough values such that it becomes about complexity and include how you measure. \$\endgroup\$ Dec 3, 2017 at 3:10
  • \$\begingroup\$ That's exactly why I was asking for input on my various ideas for scoring. I don't expect that there's going to be any programs that small that can successfully answer the question, but it could happen. I'm leaning towards asymptotic complexity or byte count. \$\endgroup\$ Dec 5, 2017 at 18:01
1
\$\begingroup\$

Advancing k-combinations

k-combinations for a set of size n represent in what different ways one can pick k elements out of a set of n elements. There is a natural representation of such a pick as an integer with n bits, of which exactly k are set.

Define next[n, k] :: Pick(n, k) -> Pick(n, k) to be the group action that takes each pick to the next one, wrapping around. More formally: Let r be an n-bit integer with k bits set. Then next[n, k](r) will return the smallest integer > r that also has k bits set. If there exists no such integer, the smallest integer with k bits is returned. Example: next[4, 2](0b0011) = 0b0101, next[4, 2](0b1100) = 0b0011.

[- Annotation: if k = 0, then there is only one unique integer with zero bits set. next[n, 0](r) = 0. -]

You will be given a pick r and a positive integer step. Output (next[n, k]^step)(r), that is, apply next[n, k] step times to r.

Rules

  • You will be given 4 integers n k r step. Output (next[n, k]^step)(r)
  • 1 <= n can be assumed to be small enough to represent picks as integers naturally in your language
  • 0 <= k <= n
  • r will always be a valid pick of k out of n.
  • 0 <= step <= C(n, k) can be relatively large. As an example, C(32, 12) = 225,792,840

Criteria

Return the correct output for all valid inputs.

This is code-golf, shortest code wins.

Examples

4   2 0b1001 2  => 0b1100
16 10 0xF11F 10 => 0bF15E
4   2 0b1100 2  => 0b0101
\$\endgroup\$
1
  • \$\begingroup\$ Nice challenge! But what if k = n = 0? And maybe specify formally how next works. \$\endgroup\$ Dec 3, 2017 at 5:38
1
\$\begingroup\$

Best Yahtzee score

Yahtzee is a game played with five six-sided dice and a score sheet with thirteen different boxes to fill a score in. Each box has its own scoring rules:

  • 1s, 2s, 3s, 4s, 5s, 6s all score points equal to the sum of the respective dice (that is, a roll of [3, 2, 3, 1, 5] scored as 3s would be awarded 6 points - 3 for each 3).
  • 3-of-a-kind and 4-of-a-kind (as they sound, three or four dice rolled the same) score points equal to the sum of all five dice.
  • Full house (two dice show one value, the other three show another) scores 25 points
  • Small straight (four consecutive values) scores 30 points
  • Large straight (all consecutive values) scores 40 points
  • Yahtzee (all dice show the same value) scores 50 points

The thirteenth (chance) makes sense in-game, but not so much for this challenge; additionally the game has bonuses for extra Yahtzees which make no sense here. Because the challenge is...

Given five dice as input (five integers 1-6, input however is convenient), output the highest score that roll can score as well as what box it's being score under. The score should be output as its decimal numeric value, whether that's an integer or a string representation thereof, whatever. It should be immediately recognizable as a number. How you identify boxes is up to you so long as they are all unique and any given roll that will be scored in a given box always returns the same value. Please specify in your answer how boxes are identified. Order ([score, box] or [box, score]) does not matter. If you're outputting to STDOUT or otherwise not returning two values from a function, please separate score and box with at least one non-alphanumeric character of your choosing.

Code golf, so shortest answer in a given language wins. Standard loopholes apply.

Test cases, using , as separator, and 123456kKfsly for the box names (respective of their order above):

in: 1 5 4 3 2
out: 40
in: 1 1 4 3 1
out: 10
in: 1 1 6 5 3
out: 6

Sandbox/meta

  • I saw one existing Yahtzee challenge, but IIRC it boiled down to scoring a whole game. I did the 'given five dice, what is the best score' exercise once and felt like there were some interesting challenges to be found in optimizing it.
  • Better ways to express I/O? I want it to be flexible but relatively readable...
  • My first potential submission, I'm sure I'm forgetting something...
\$\endgroup\$
5
  • 2
    \$\begingroup\$ IMO, multi parts output is pretty much a party killer. In that specific question, I think the score itself is enough to constitute a nice challenge. The box value is drived by conditional programming, which (of the challenge goes well) might not be present in some answers. \$\endgroup\$
    – Uriel
    Dec 6, 2017 at 22:58
  • 1
    \$\begingroup\$ Anyway, for that wide range of possibilities, you should add at least one test case to cover collisions, multiple scorings and at least one of each box type (again, as I see challenges here) \$\endgroup\$
    – Uriel
    Dec 6, 2017 at 23:00
  • \$\begingroup\$ @Uriel Thanks for the input — I planned to fill in more test cases, I guess I could've mentioned that in the meta section. I'm not trying to be difficult, but I'm curious if you could expand on your other point w/ the score itself being enough. The score is (I believe?) entirely dependent on the box being determined, and spitting something box-related out seems programmatically like a small challenge vs. the 'reward' of the output. This was why I wanted that output to be very flexible. Part of me thinks you're right, part of me thinks I'm right… so if you have more to say, please do… \$\endgroup\$
    – brhfl
    Dec 7, 2017 at 2:37
  • \$\begingroup\$ my point is, in order to get the right score the user necessarily went through the right box (and not even print it, but also did a somewhat-more-complex calculation with it) - so it's kinda like letting them output twice. \$\endgroup\$
    – Uriel
    Dec 7, 2017 at 10:02
  • 1
    \$\begingroup\$ @Uriel Makes sense, and I was leaning that way the more I thought about it last night. Cutting it also eliminates the need to address collisions. I think it's out... Thanks! \$\endgroup\$
    – brhfl
    Dec 7, 2017 at 13:35
1
\$\begingroup\$

Google Doodle Kids Coding-style simulator

One input is a list of commands. There are three action commands and a loop construct. There is some flexibility as to the command format:

  • As a string or equivalent: The loop construct should use a pair of matching brackets. The direction commands should be < and > or L and R (either case). The motion command should be ^ or F.
  • As a list of characters: The loop construct should be a sublist. The other commands should be individual characters in the list, specified as above.
  • As a list of integers: The direction commands should be -1 and 1 while the motion command should be 0.

The other input is the starting position. This consists of an two-dimensional array in any suitable format (including a newline-separated string). Background values should be represented using 0 or spaces. Carrots should be represented using -1, ^ or V (either case). The starting square should be represented using 1, @, or R (either case).

Optionally, the starting direction can be an input (one of <>V^ or an angle in degrees or turns), or it can be hard-coded (please specify the default starting direction in this case).

Command rules:

  • Loops always execute four times
  • The direction commands rotate the rabbit in place
  • The motion command moves the rabbit one square in the current direction

The rabbit wins if it eats all of the carrots.

The rabbit dies if:

  • It runs out of commands
  • It walks out of bounds
  • It walks onto the background

The starting square and carrot squares are all safe.

Your output should be a consistent truthy value if the rabbit wins, and a consistent falsy value if it dies. This can also be achieved by exception or error exit.

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

\$\endgroup\$
8
  • \$\begingroup\$ Related \$\endgroup\$
    – Emigna
    Dec 8, 2017 at 11:51
  • \$\begingroup\$ What's the background? \$\endgroup\$
    – DELETE_ME
    Dec 8, 2017 at 12:07
  • \$\begingroup\$ 1) exception exit is already a standard way to output a falsey value, and 2) in the actual Google doodle you don't lose if you try to walk off the edge of the map, it just does nothing. \$\endgroup\$
    – Nissa
    Dec 8, 2017 at 14:02
  • \$\begingroup\$ @StephenLeppik It's not meant to exactly simulate the Doodle. \$\endgroup\$
    – Neil
    Dec 8, 2017 at 14:32
  • \$\begingroup\$ By "background" I means as in "It walks onto the background". \$\endgroup\$
    – DELETE_ME
    Dec 9, 2017 at 10:04
  • \$\begingroup\$ @user202729 The background is any square whose value is 0 or space depending on your input format. \$\endgroup\$
    – Neil
    Dec 9, 2017 at 10:55
  • \$\begingroup\$ Ready to post to main? \$\endgroup\$
    – DELETE_ME
    Dec 11, 2017 at 5:48
  • \$\begingroup\$ Don't abandon this... :( \$\endgroup\$
    – DELETE_ME
    Dec 18, 2017 at 15:43
1
\$\begingroup\$

Tell my browser

Background

Many people visit webpages, which require special browsers because of lack of compatibility. So you have to write a script (client sided or server sided), which just prints the name of the browser. Because not everyone has fast internet, the script has to be as short as possible.

Rules

  1. You have to print the name of the browser loading the page without any version number etc. to STDOUT or equivalent. Leading or trailing spaces are allowed.
  2. You can assume the browser is Firefox, Chrome, Edge, Safari or Opera, so only those browsers will be tested. Don't print "Chromium", this does NOT count.
  3. The script may be server sided with CGI (in any language), ruby on rails, jsp and similar. Client sided scripts may be written in JavaScript, TypeScript, and any other versions of ECMAScript, it just has to run in all five browsers.
  4. If your language has no offline interpreter for CGI, assume it's saved in /usr/bin/i, the shebang at the beginning does not add bytes to the count.
  5. this is a , so the shortest answer wins!

Meta

  • Does this question have important loopholes?
  • Is there any language which cannot be programmed in? (CGI should work always, even Java or bf could be done with a shebang, lol)
\$\endgroup\$
4
  • \$\begingroup\$ About the "Is there any language which cannot be programmed in?" --- that's actually a very good question. Let me try. \$\endgroup\$
    – DELETE_ME
    Dec 10, 2017 at 14:37
  • \$\begingroup\$ About the background... "fast internet" doesn't matter if the script is server-side. \$\endgroup\$
    – DELETE_ME
    Dec 10, 2017 at 14:38
  • \$\begingroup\$ @user202729 This is a joke, lol, just like those other joke reasons the program has to be short. Is it a good question though? \$\endgroup\$
    – univalence
    Dec 10, 2017 at 14:49
  • \$\begingroup\$ Probably. But the fact is, not everyone is familiar with writing a server, so you may not get a lot of answers. \$\endgroup\$
    – DELETE_ME
    Dec 11, 2017 at 6:03
1
\$\begingroup\$

Coin Game: Shoot It Out!


In Shoot It Out, we will play with coins on a table.

Basic Idea

Shoot It Out is a 6-player game. The players will be split into two teams of 3 players, one offensive, and one defensive.

Initially, every player has a coin on the table. Additionally, there is a target coin. Players take turns to shoot their coin. However, the shots will not be very accurate.

The offensive team will try to shoot the target coin out of the table, while the defensive team tries to prevent the target coin from being shot out. You should make a bot that can play as both offensive and defensive team, and try to maximize the winning rate.

Rules

Playing Order

  • Every player has its player ID. ID 1, 3, 5 are on the offensive team; ID 0, 2, 4 are on the defensive team.

  • Playing order is the same as ID. After the turn of ID 5 is ID 0's turn. If a player is removed, simply go to the next player.

  • When it is a player's turn, they will shoot their coin once. After every coin stopped moving, the turn ends.

Elimination in a Game

  • If a player shoots their own coin out of the table, the player is removed from the game. If the target coin moves out of the table in the same turn, it will be placed back to the previous position.

  • If a player shoots another player's coin out of the table, both players are removed from the game.

(Note that these two can occur in the same turn.)

Winning Conditions

  • Defensive team wins when both conditions below are satisfied:

    • The target coin is in the table area.
    • All players on the offensive team are removed, or 18 turns have been played (skipped turn is not counted).
  • Offensive team wins when one of the conditions below are satisfied:

    • The target coin is out of the table area.
    • All players on the defensive team are removed.
  • There is one exception: if all players are removed at the end of a turn, the defensive team wins.

Table Settings / Parameters

  • The table is a circular area of radius 100 cm. The radius of every coin is 1 cm. A coin is out of table iff its center is out of the circular area.

  • For convenience, we set the coordinate of the center of the table to (0, 0), and denote the position of a coin by the coordinate of its center.

  • The coefficient of restitution between coins is 0.9.

  • The maximum intended speed of a shot is 240 cm/s.

  • When a coin is moving, it will have an acceleration of -240 cm/s^2 (due to friction).

  • When the game starts, the target coin is located at (0, 0), while the coin of ID x is located at (2.5 cos(f(x)*pi/3), 2.5 sin(f(x)*pi/3)). The values of f(x) are:

x f(x)
0 0
1 3
2 1
3 4
4 5
5 2

Here is a picture of initial positions.

Errors

Each player's shot has two parameters: angle and initial speed. Programs will output the two parameters representing its intended shot. However, the actual shot won't be the same of what is intended: errors will be added into parameters.

Specifically, if the angle (in radians) and initial speed (in cm/s) of the intended shot are θ, v, then:

  • The actual angle will be θ+R(pi/70).

  • The actual initial speed will be v*exp(R(1/12)). (Note that it may exceed the maximum speed.)

Where R(x) is a random variable with Gaussian distribution of standard deviation x and average 0.

Scoring

Since only 6 players can play in one game, the controller will randomly assign players to a game.

Lots of games will be held until each player has played both defensive and offensive team in more than 10000 games.

The final score of your program will be y/x+z/(1-x), where:

  • x is the average winning rate of offensive team in all games.

  • y is the winning rate of your program when on the offensive team.

  • z is the winning rate of your program when on the defensive team.

Input / Output

Your program will be run once per game. It should receive inputs from stdin and output to stdout.

At the beginning of a game, it will receive a line of input a, where a is the player ID (thus indicating which team you should play in).

When a turn starts, you will receive input like this:

3
0 3.798 3.332
1 12.656 3.666
3 18.652 7.913
4 8.004 7.132
6 -3.187 -9.553

The first line indicates the player of this turn. Each remaining line contains information of a coin: The first number is the player ID of the coin's owner (or 6 if it is the target coin). The remaining two numbers are x and y coordinates of the center of the coin.

If it is your turn, you should output two numbers, separated by a newline or space, representing the intended angle (in radians, 0 is +x, pi/2 is +y) and initial speed (in cm/s). You should flush stdout after output. (If it is not your turn, you should not output anything.)

You needn't to handle the termination of your program. When the game ends (or you are removed), the controller will send SIGKILL to your program to terminate it.

Specifications

  • Your program should be able to be compiled into an executable, or be executed like an executable (for example, add shebang if you use interpreted languages). If your program need to be compiled to run, you should also specify how to compile your program.

  • Your program should not access files, or anything that stores information between games.

  • Your program should be deterministic. You can use random number generators, but you should make sure that the generator you use is based on a fixed seed, and will not use random devices (such as RDRAND or /dev/random), system time, etc.

  • All "random" numbers (while generating errors and assigning players) used by the controller are generated in a deterministic way. However, your program should not take any advantage of it.

  • The total response time of your program in a game should not exceed 0.1 second.

  • You can submit multiple programs, but they should not team up against the others.

Controller & Sample Bots

(Still working on them...)

\$\endgroup\$
1
\$\begingroup\$

The 64 | 64 Color Selector

All colour selector tools suck. Let us make another one that sucks also, but in a different way.

Your interface will have:

  • two squares, of 64x64 "pixels" each one. Pixels do not need to be strictly pixels, but anything where the user can have 64 possible selections in each direction, vertical or horizontal, representing all the possible different RGB colors.

  • a third element of the interface that will represent the color selected with user has selected based picked on squares.

  • a fourth element which represents the 6 digit hexadecimal RGB hex-code (example: #FFBF32). You can divide it in three elements, but you have to make clear which component is what from RGB.

  • a fifth element which represent the decimal RGB code (example RGB(127,33,43)). You can also divide it in three elements, but you have to make clear which component is what from RGB.

When the two squares are at the top left corner, selected color must be RGB(0,0,0); and when the two squares at the bottom right corner must be RGB(255,255,255).

You must have the the pixels in the square sorted by increasing order; I don't care what direction, vertical or horizontal, you choose for increasing one-by-one, but the two squares must have the same pattern.

When the user picks a "pixel" in the first square, the colours of the second must be updated and reflect all possible values under the second pixel.

When the user picks a "pixel" in the second square, 3rd, 4th and 5th elements must be updated to reflect new color selection.

Code-golf, but there will be no accepted answer, as it discourages people from adding new answers when they see already posted very short answers.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Your specifications seem a bit too loosely-defined to me, though unfortunately I don't have any suggestions for improvement at the current moment \$\endgroup\$
    – hyper-neutrino Mod
    Dec 11, 2017 at 15:32
  • \$\begingroup\$ I assume that your first requirement should state 'Pixels do not need to be strictly pixels...' \$\endgroup\$
    – brhfl
    Dec 11, 2017 at 18:34
  • \$\begingroup\$ @brhfl Yes. Thanks. Fixed. \$\endgroup\$
    – sergiol
    Dec 11, 2017 at 18:50
  • \$\begingroup\$ Is there any requirement on the ordering of selections in the first two elements, or is it fine as long as every RGB color could be expressed as a coordinate pair on the first element plus a coordinate pair on the second element? \$\endgroup\$ Dec 11, 2017 at 19:21
  • \$\begingroup\$ @KamilDrakari: Yes. Thanks. Updated. \$\endgroup\$
    – sergiol
    Dec 12, 2017 at 11:09
  • \$\begingroup\$ @HyperNeutrino: better now? \$\endgroup\$
    – sergiol
    Dec 12, 2017 at 11:10
  • 1
    \$\begingroup\$ It looks good, you may want to point out that you want a 1:1 color conversion. I was looking at it and I think that's what you want since 64^4 = 256^3. \$\endgroup\$
    – Neil
    Dec 13, 2017 at 4:03
  • \$\begingroup\$ "You must have the the pixels in the square sorted by increasing order" is nonsense unless you address the issue that HyperNeutrino raised about the specifications not truly being specifications. \$\endgroup\$ Dec 13, 2017 at 9:41
1
\$\begingroup\$

Sheet music exact transposition

As we're limited to ASCII here, I'll just refer to the notes by name A-G, although obviously real sheet music has a range of about an octave and a half even before you take ledger lines into account.

Notes are written on sheet music in two ways. Most of the time, notes have their own position on the stave, but no accidental is indicated; this means that the note gains the accidental corresponding to the key signature. For example, the scale of A is ABCDEFGA; the C, F and G are played sharp because of the key signature. These notes are easy to transpose, because you simply need to shift them by the appropriate number of note names; the accidental is taken care of by the key signature. For example, the scale of A is simply ABCDEFGA; if you transpose down two notes, you get the scale of F, FGABCDEF; in this case the C, F and G become natural and the B becomes flat, but there's nothing extra for you to do here because the key signature takes care of it. This works even if the key itself contains accidentals; transposing the scale DEFGABCD from D♭ to D♯ simply results in DEFGABCD again.

For notes that are not available in the key signature, an accidental needs to be applied. This is either the ♮, indicating that an accidental in the key signature (or previously used for that note, but that's not relevant here) should be ignored, or one or more of either ♭ or ♯, indicating how many semitones the note should be adjusted. (Although an accidental exists for ♯♯, we will ignore this to simplify the challenge).

You can't just throw accidentals around, otherwise you end up with the scale of E written as F♭E♯♯A♭A♮C♭B♯♯F♭♭E which is ridiculous. It is therefore essential when you transpose a note that the note name is transposed identically no matter how many accidentals the note may have.

However, there is a caveat: the named intervals are not regular. The interval between B and C and that between E and F are just one semitone, while the other intervals are two. This means that you might have to adjust the accidental if the number of semitones between your original and transposed note differ from that of the original and transposed key. The number of accidentals in the key must also be taken into account, of course.

Take the example of transposing the note D from the key of A to the key of F. Because F is five notes above A, the note D transposes to the note B; the key signature takes care of making the B flat. However, if we were transposing the note D♯, we would have to calculate that the final note needs to be B♮ in order for the number of semitones to be correct (F - A = 8, B♮ - D♯ = 9 - 1 = 8; the ♯ increase the number of semitones while the ♭ decreases it, but of course subtracting a ♯ results in a decrease too).

Conveniently, the output has an accidental of some sort (including ♮) if and only if the input note does, which should simplify the challenge.

Your challenge is to write a program which will accept three notes as arguments. Two of the notes will represent the original and transposition key of the transposition, while one of the notes will represent the note to be transposed. You must then output the result of the transposition. Examples:

Note    From    To      Result
G♮      A♭      B♭      A♮ (not A)
C♯      B       D       E♮ (not E)
B       F       D       G
B♭      C       G       F♮
B       B       A       A
B       E       B       F (not F♯)
D♭      E       G♭      F♭♭ (not E♭ or D♯)
G♭      E       G       B♭♭ (not A or A♮)
E♭      G♭      C♯      A♮ (not A)
C       F       D       A
G♯      C       G       D♯ (not E♭)

This is , so the shortest program wins. However, since there does not appear to be an ASCII character that can represent ♮, I will allow any of the three UTF-8 characters ♭, ♮ or ♯ to count as a single byte.

\$\endgroup\$
1
\$\begingroup\$

Simultaneous Selection

In the game Risk of Rain there is a game mode where you can select which items you want out of dropped boxes. The only problem is that when you open two boxes at the same time your movements in one box effect your movements in another. Now this can be a problem since you may want to retrieve a particular item from one of the boxes. However there is a solution.

Since the boxes have different shapes and you are not permitted to move your cursor outside of the box you can desynchronize the two cursors.

For example if we have the two boxes

S.F...    S.....
......    ...F..
....      .....

Where F is the goal and S is the starting location, we can get the cursor to the goal by moving the cursor

Right 4 times
Down 3 times 
Up 1 time
Left 1 time

Still working on it ...


Input

As input you will receive two 2 dimensional boolean containers, representing the shapes of the boxes. In these boolean arrays true means that square exists in the box false means square does not exist. You may assume that your input will be padded with false values such that no true values touches the edge of the array.

You will also receive two coordinate pairs representing the start and end locations.

Output

You should output a ordered container of "moves" such that when performed on both boxes the cursor will arrive at the end point. A "move" may be one of 4 chosen values each representing one of the 4 cardinal directions. For example you might choose: [N,S,E,W], [1,2,3,4] or [(1,0),(0,1),(-1,0),(0,-1)]. Your program must be self consistent in these values across multiple sessions.

If no solution is possible for the given boxes you must output a value that is distinct from any possible sequence of moves, for example a list containing a 5th value that cannot represent a move, or a non list item.

Still working on it ...

\$\endgroup\$
2
  • \$\begingroup\$ How do we take input? As two separate strings or can it be arrays, etc... \$\endgroup\$
    – Neil
    Dec 17, 2017 at 5:20
  • \$\begingroup\$ @Neil Its going to be boolean arrays, true means square exists false means square does not exist, and coordinates for start and end locations. I've been a little lazy in finishing this question. \$\endgroup\$
    – Wheat Wizard Mod
    Dec 17, 2017 at 5:22
1
\$\begingroup\$

Demolish a string! v2

A modified version of Demolish a String; since the original question involved randomness, the challenge was too complex and there were not many answers. This challenge removes the criterion and allows flexibility by the answerer, which should invite responses in languages without randomness built-ins.

Challenge

Given a string input, output the demolished version of it.

The Process

P
r      Pr       r
o       o       o
g       g       g
r       r       r      rogr         r
a  ->   a  ->   a  ->     a  ->     a  ->           ->           ->           ->           ->  
m       m       m         m         m
m       m       m         m         m         mmar         m
i       i       i         i         i         i            i           mi           m
n       n       n         n        gn        gn           gn           gn           gni         mgni
g       g      Pg        Pg      roPg      roPg         roPgmar      roPgmar      roPgmar      roPgmar

Place the string vertically. Repeat the following steps until they are impossible:

  1. Take any column of characters that can be demolished (explained below)
  2. Select some integer between 1 and (height of the column of characters) - 1 and some direction (left or right).
  3. Rotate that number of characters in that direction (only if those spaces are unoccupied; if not, go back to step 3).
  4. Let those characters fall due to gravity.

At the end, the output should be a string whose heights of consecutive columns differ by at most one.

Note: the choice of integers and the direction is up to the answerer

If there are space characters in the input, demolish those first, all at once.

C
o

d      
e  ->     oC  ->         ->  ...
       de         
G        G          G
o        o          o
l        l          l
f        f        defoC

Rules

  • Standard loopholes are forbidden.
  • Trailing and leading newlines are allowed.
  • Your program may either print or return a string/equivalent.
  • Please explain the demolition algorithm (# of characters and direction) in your answer.

Some test cases to try

A
Programming
Code Golf
The quick brown fox jumps over the lazy dog

This is , so the submissions with the smallest byte counts in their languages win!

\$\endgroup\$
1
\$\begingroup\$

Program an Uncircularness Score

derivative of this challenge

Meta:

This is just a rough idea for a slightly different challenge. I have no idea how successfull it would be in the current state, so feel free to share your opinions and suggestions.

Your task is to program a mathematical function s, that takes a finite set A of points in the 2D plane, and outputs an uncircularity score s(A) that satisfies following properties:

  1. positive definiteness: If there is a circle or a straight line that contains all points of A, then s(A) = 0. Otherwise s(A) > 0
  2. It is surjective to the nonnegative real numbers, that means for every nonnegative real number r there is a finite subset A of the plane such that s(A) = r.

Scoring

You get one point for every of the following properties that your function (provably) has.

  • Translation Invariance: s is translation invariant if s(A) = s(A + v) for every vector v and for all A.
  • Scale Invariance: s is scale invariant, if s(A) = s(A * t) for every t≠0 and for all A.
  • Monotony: s is monotonous if s(A) ≤ s(B) for all A,B where A ⊆ B.
  • Circle Inversion Invariance: s is circle inversion invariant, if s(A) = s(f(A)) for all A with 0 ∉ A, where f(x,y) = (x/(x^2+y^2), y/(x^2+y^2)) is the circle inversion. (Here (x,y) represent the cartesian coordinates of a point in the plane.)
  • Triangle inequality: s satisfies the "triangle inequality" if s(A ∩ B) ≤ s(A) + s(B) for all A,B. (This is implied by Monotony.)
  • Reverse triangle inequality: s satisfies the "reverse triangle inequality" if s(A) + s(B) ≤ s(A ∪ B) for all A,B.
  • Continuity. s is said to be continuous if the function f(p) := s(A ∪ {p}) (mapping the a point p to a real number) is continuous using the standard absolute value on the real numbers, and the standard euclidean norm on the points of the plane.
  • More to come...
\$\endgroup\$
10
  • \$\begingroup\$ Perhaps you should change the "non-negative real number" to "non-negative rational number" or "non-negative algebraic number" in part 2. If these functions are being produced by code it seems quite unreasonable to expect numbers that cannot be represented in computer memory to be output. \$\endgroup\$
    – Wheat Wizard Mod
    Aug 26, 2017 at 17:13
  • 1
    \$\begingroup\$ @WheatWizard That's an interesting thought. Personally I quite like the idea of these properties working over the real numbers in theory, and the code implementing it to a desired accuracy of approximation, but I'm not sure if that's easier or harder to score/judge valid. \$\endgroup\$ Aug 26, 2017 at 17:18
  • \$\begingroup\$ @trichoplax I will admit I am opposed to any "code must work in theory" rules in challenges. However any code that works in theory must also work on the reals or algebraics which allows us to have code that works not just in theory. \$\endgroup\$
    – Wheat Wizard Mod
    Aug 26, 2017 at 17:22
  • \$\begingroup\$ @WheatWizard I agree that asking for testable solutions is much more satisfactory than "works in theory". \$\endgroup\$ Aug 26, 2017 at 17:30
  • \$\begingroup\$ I guess "provably" needs to be defined in the context of the challenge. Will there be a defined method of testing or does this require a mathematical proof (in which case it leans more towards puzzling's scope). \$\endgroup\$ Aug 26, 2017 at 17:32
  • \$\begingroup\$ @WheatWizard That is a good point that I did not think about. But I'd allow for limited precision implementations (i.e. floating point), because everything else would probably almost make the challenge impossible. \$\endgroup\$
    – flawr
    Aug 26, 2017 at 18:58
  • \$\begingroup\$ @trichoplax You'd need a lot of testcases to be convincing, but I think the participants should be able (they don't have to write down proofs) to provide good arguments for why a certain property is satisfied, just as we require any program to be actually doing what it is supposed to do. (we don't require proof of correctness either) \$\endgroup\$
    – flawr
    Aug 26, 2017 at 19:01
  • \$\begingroup\$ I think trichoplax makes a good point. I'm not sure how much this is really about code. It might be a better idea to post this on puzzling as a math puzzle where you need only define a function rather than some code. \$\endgroup\$
    – Wheat Wizard Mod
    Aug 26, 2017 at 19:03
  • \$\begingroup\$ @WheatWizard Thanks. I think this could be made into a code-challenge (or code-golf), but it could also be made into a mathematical function challenge like you suggest. I can't guess which would be more interesting (or easier to define objectively) though. I suppose there's nothing stopping it being two challenges, one on each site... \$\endgroup\$ Aug 26, 2017 at 20:18
  • \$\begingroup\$ Translation and scale invariance are easily added: translate to put the centroid at the origin and then if there's more than two points scale so that the furthest point from the origin is at distance 1 from the origin; then apply the original function. It might be possible to deliberately construct a noncircularity function such that this would destroy the surjectivity, but in practice I don't think the question would be harmed by assuming that all answers will be affine-invariant and simplifying the scoring system appropriately. \$\endgroup\$ Aug 27, 2017 at 17:09
1
\$\begingroup\$

Squeeze Out a Square Quine

...the bigger the better.

Task

Write a full program that is a proper quine (a piece of code that outputs itself without reading its source code). To make things more difficult, your code (and obviously the output) has to be in a form of a square, meaning that your code must consist of n lines of length n (not counting the newline to the line length).

Scoring

Your answer's score will be n, the side length of the square. The largest square quine wins. To avoid answers being padded to create arbitrarily large squares, your code must fail to be a proper quine if any single non-newline character is replaced by some other character that appears in the code. There must be, at minimum, two different non-newline characters in the code.


For example, if your code was...

abc
def
ghi

...and would output itself, your answer would be valid and its score would be 3.

A single trailing newline in the output is allowed.

\$\endgroup\$
6
  • \$\begingroup\$ Replace single character at one places or multiple characters at multiple places? \$\endgroup\$
    – DELETE_ME
    Dec 27, 2017 at 3:27
  • \$\begingroup\$ @user202729 I was thinking of single character at one place, but I'm not sure if it's sufficient. \$\endgroup\$
    – Steadybox
    Dec 27, 2017 at 3:31
  • \$\begingroup\$ If it's a quine then surely it should be a trailing newline in the code \$\endgroup\$
    – Jo King Mod
    Dec 27, 2017 at 10:38
  • \$\begingroup\$ In that case it should be "the source code and the output may differ at the trailing newline". Also, if the restriction is "multiple character at multiple places" then it would be near impossible, because it's likely that there are multiple valid programs for each square size. \$\endgroup\$
    – DELETE_ME
    Dec 29, 2017 at 6:13
  • \$\begingroup\$ I like the challenge but at a certain size, checking a solution for its validity will be impossible. What if someone posts a solution and failed to notice some weird replacement that would render that submission invalid? \$\endgroup\$ Dec 30, 2017 at 14:13
  • \$\begingroup\$ @BruceForte Yeah, it's pretty problematic a challenge. I'm not sure what to do with it. Perhaps it would work better as code-golf. \$\endgroup\$
    – Steadybox
    Jan 3, 2018 at 6:00
1
\$\begingroup\$

Shortest Path Distance

Uh oh! You want to get to the point (10,10) from the origin, but there are a whole bunch of boxes in the way! What is the length of the shortest path which avoids all of them?

Input

Your program should take a set of rectangles, defined by the coordinates of two opposite corners, as input; the format is up to you.

For example, a possible input might look like

[[(1,3), (5,2)], [(5,4), (7,5)]]

But you could also take it as

[(1,3), (5,2)]
[(5,4), (7,5)]

Or anything else, as long as it allows for unambiguous input.

These inputs would define the rectangles shown below: Minimum path length to A from (0,0): sqrt(10) + sqrt(130), approx 14.564

You can assume that all rectangles will have integer coordinates with x,y between 1 and 9 inclusive, which guarantees a possible path. You can also assume that no rectangles intersect in any way (that means no shared edges or vertexes).

Output

Your program/function must return the value of the shortest path from the origin to (10,10), have the absolute error at most 10-2 and measured using the euclidean metric.

In the example given above, 14.564 and 14.56 would be accepted, while 14.55 and 14.57 would not.

Example I/O

[[(1,3), (5,2)], [(5,4), (7,5)]] -> 11.40
[] -> 14.14
[[(1,1), (2,9)], [(9,2), (3,1)]] -> 14.28
[[(2,2), (1,1)], [(9,3), (8,5)], [(1,9), (2,8)]] -> 14.28 (Note: rounded up)
[[(9,1), (1,9)]] -> 18.11

Other Rules

Shortest code wins, no exploiting loopholes, yadda yadda yadda, you get the idea, it's code golf.

\$\endgroup\$
12
  • \$\begingroup\$ The taxicab (Manhattan) distance is always 20. I don't know Taxi PL, but I suppose it is not too hard to write. \$\endgroup\$
    – DELETE_ME
    Nov 15, 2017 at 4:58
  • \$\begingroup\$ @user202729 Not true in the case that backtracking is required. \$\endgroup\$ Nov 15, 2017 at 5:30
  • \$\begingroup\$ Using taxicab distance instead of manhattan distance makes the challenge slightly easier and more accessible to languages that can't handle floating-point well. \$\endgroup\$ Nov 15, 2017 at 5:31
  • \$\begingroup\$ @Challenger5 Why does output 20 require backtracking??? \$\endgroup\$
    – DELETE_ME
    Nov 15, 2017 at 9:18
  • \$\begingroup\$ @user202729 If backtracking is required (e.g. the blocks form a spiral shape), then the taxicab distance will be >20. \$\endgroup\$ Nov 15, 2017 at 16:56
  • \$\begingroup\$ @Challenger5 No, all rectangles will have integer coordinates with x,y between 1 and 9 , which means that you can always move (0, 0) → (0, 10) → (10, 10), which have taxicab distance = 20. \$\endgroup\$
    – DELETE_ME
    Nov 16, 2017 at 1:13
  • \$\begingroup\$ Ready for posting to main? \$\endgroup\$
    – DELETE_ME
    Jan 7, 2018 at 13:22
  • 1
    \$\begingroup\$ Alternatively, you could ask not for the length of the shortest path but for the actual path! \$\endgroup\$
    – flawr
    Jan 8, 2018 at 13:21
  • \$\begingroup\$ @flawr ... Isn't that harder? I don't know... \$\endgroup\$
    – DELETE_ME
    Jan 10, 2018 at 10:50
  • \$\begingroup\$ @user202729 How else would you calculate the length of a shortest path if not by explicitly finding a shortest path? \$\endgroup\$
    – flawr
    Jan 10, 2018 at 10:53
  • \$\begingroup\$ What if we have two rectangles that touch eachother but do not share edges or vertices, like [(0,0),(2,1)] and [(1,1),(3,2)]? Also: Can we e.g. assume a certain representation of the rectangles (i.e. always first the top left vertex, then the bottom right)? \$\endgroup\$
    – flawr
    Jan 10, 2018 at 10:56
  • \$\begingroup\$ @flawr Unfortunately, it seems that the OP abandoned this... Also, Dijkstra algorithm. (it calculates the shortest distance from source to all points, so by triangle inequality you can deduce the path, but it definitely takes more code than just outputting the distance) \$\endgroup\$
    – DELETE_ME
    Jan 10, 2018 at 11:00
1
\$\begingroup\$

Any comments for improvement would be appreciated.
Should I choose a harder function? (maybe "Is this binary number prime?")
Or maybe not harder, but some other decision problem suggestion?

Majority function, a non-uniform computing challenge

Non-uniform computing is a class of computing where a different procedure can be specified for each input size of a problem. This allows discussing complexity of languages that are only straight line computations (no looping constructs), yet which are powerful enough to compute any fixed input size function a Turing machine can compute. It also allows taking advantage of algorithms that may work well if only you could tweak a parameter for each size (even if the parameter is difficult to compute) or where there are only a small number of exceptions in each input size (so checking those exceptions then using the algorithm succeeds).

Goal:

Write a program or function which, given an input length, outputs an If-Then-Else sequence (defined below) which determines if greater than half the inputs are 1 (the majority function).

This is . Your score will be:

G20 + 4*G5 + 10*G2 + L

Where L is the size of your submission in bytes, and G20 is the length of the generated If-Then-Else sequence for size=20 (length being defined as number of If-Then-Else statements). Similarly G5 and G2 are the lengths for the generated programs for size=5 and size=2 respectively. The lowest score wins.

This is in some sense an "inception" code golf. You will be judged on the length of your program as well as the length of the programs it generates.

To prevent submissions that just loop over all possible ITE sequences till it finds the smallest one that works, entries need to provide the G20, G5, G2 values along with the code submission for it to be a valid entry. As the number of possible sequences quickly becomes infeasible to search, this should eliminate raw brute forcing.

If-Then-Else "programs"

An If-Then-Else (ITE) statement is a logical statement of the form:

if A then B else C

The logical value of this statement is referred to as the "output", and the values A, B, and C are the "inputs" of the statement. To turn this into a formatted language, a file (or string) describing an ITE program will be a series of lines that contain:

<input_term> <space> <input_term> <space> <input_term>

Where an input_term is one of:

  • '0'
  • '1'
  • 'I' <decimal_number>
  • 'Q' <decimal_number>

The values 0 and 1 are Boolean false and true respectively. The value of I(number) is the value of the input at index 'number'; for example I3 = Input #3 (input numbering starts at zero). The value of Q(x) is the result of ITE statement number 'x' (again, numbering starts at zero).

The result of an ITE program is the output of its last statement.

Example ITE program

Here is a simple interpreter for ITE programs, written in python: ite.py

This interpreter has some additional features like comments (start a line with #) and custom output names (start line with <name>: ) which are useful when playing with some ideas by hand. If you choose to utilize those features in your generated ITE programs, that's fine, although I'm not sure how that would help. This will be considered the defacto standard for the ITE language for this competition.

Here is an example program: parity4.ite

I0 0 1
I1 Q0 I0
Q1 0 1
I2 Q2 Q1
Q3 0 1
I3 Q4 Q3

As its name suggests, this is the parity function for input size 4. It returns 1 if the 4 inputs bits have an odd number of 1s, otherwise it returns 0. Here is an example of testing it on some values.

$ python ite.py parity4.ite 0110
0
$ python ite.py parity4.ite 0111
1
\$\endgroup\$
4
  • \$\begingroup\$ Welcome to PPCG, this is a great challenge! I haven't put much thought into it but what's the reason for such a high weight on G2? G2 could become a special case for some clever approaches (just a guess) in which case it would be quite a hefty penalty (or they would have to hardcode its output). \$\endgroup\$ Jan 17, 2018 at 15:06
  • \$\begingroup\$ @BMO I think the required number of statements may scale roughly proportional to the number of inputs. So I was trying to "weight" them evenly. Now that you mention it, G2=1 is possible, so maybe that is not a good one. \$\endgroup\$
    – PPenguin
    Jan 17, 2018 at 16:59
  • \$\begingroup\$ I was hoping to test both a "small" input size (easy to solve by hand), "medium" input size (hopefully possible to at least follow by hand), and "large" input size (probably too big to follow by hand). I guess G2 is too small. Maybe it would be better to just check G20 and G5? \$\endgroup\$
    – PPenguin
    Jan 17, 2018 at 17:04
  • \$\begingroup\$ I haven't tried it yet, so it's difficult to say but G2 is not very interesting and it has quite a significant weight. I didn't mean that you should exclude it, but maybe it's a good idea or at least change the weights - maybe using G3 would be an option as well, I think it's a good idea to use small ones that are verifiable by hand. Tbh. finding out a good weighting system is not easy, maybe others with experience could help you out there? \$\endgroup\$ Jan 17, 2018 at 18:06
1
\$\begingroup\$

Solve the Square-Sum problem

Based on these (very good) Numberphile videos:

The Square-Sum problem and its extra footage.

The Problem:

Given a list of integer numbers [1,n] where n≥15; n≠18, 19, 20, 21, 22, 24, your task is to arrange those numbers in a way such that the sum of two consecutive numbers is a square number.

Example for n=15:

Original sequence: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Square-sum of it: 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9
                   | |  |  | | |  |  | | |  |  | | |
                  3² 4² 5² 4²3²4² 5² 4²3²4² 5² 4²3²4²

This problem can be solved by creating a graph of every sum of two numbers in the sequence that result in a square number:

Graph

From that graph, it's possible to find its Hamiltonian Path:

Hamiltonian Path

This path, if existing, is the solution to the square-sum problem.

Rules:

---Under Construction---

Sandbox:

  • Suggestions?
  • Dupe?
  • Test cases are under construction
\$\endgroup\$
1
1
\$\begingroup\$

Word ladder

A word ladder is a puzzle where the aim is to create the smallest sequence of steps between two fixed words (a starting word and a target word), where each step changes one letter to produce a new word. All the intermediate words must be recognised in a dictionary (which will be supplied).

If the target word is longer than the starting word, a step may add a letter at any position instead of changing one; if it's shorter than the starting word, a step may remove a letter instead of changing one.

Examples:

HAND
BAND
BOND
FOND
FOOD
FOOT
FINGER
FINER
FINE
TINE
TONE
TOE
EYES
EYED
DYED
DEED
TEED
TEND
TENT
TENTH
TEETH

The challenge

Write a program or function which accepts a dictionary of words and the two fixed words (i.e. a starting word and a target word), and produces an ordered list of intermediate words following the rules above. You may choose to output the starting word, the target word, both, or neither.

You may use any of the standard methods of input and output, and must not bypass the rules with any of the standard loopholes.

Scoring

(I need some help with this part).

The score is the number of dictionary lookups your program makes during a test run (or average of several test runs, if it's not deterministic) on a set of inputs with a simple English dictionary. Q: does this test set need to be prepared and included in the question?


Sandbox questions

I don't really want to make this a , as we'll just end up with simple brute-force algorithms; I really want to see creative use of the dictionary, either by pre-processing or perhaps by ordering candidate words.

Is there a way we can define a "dictionary lookup" and somehow separate the word generation/validation from knowledge of the fixed words, without making assumptions that the language has functions or other methods of isolating code?

Can we require the dictionary to be a separate process, and provide a reference implementation? I don't think we can, without excluding languages without reasonable inter-process communication (I'm thinking of PostScript, possibly JavaScript, and microcomputer BASIC).

\$\endgroup\$
9
  • \$\begingroup\$ I think this could be a test-battery challenge, with both different words and different dictionaries as tests. Different dictionaries are needed to avoid languages searching in a build-in English dictionary and only validating their finds in the provided dict. \$\endgroup\$
    – Laikoni
    Jan 18, 2018 at 14:33
  • \$\begingroup\$ I mentioned English because I would like entries to be able to use heuristics to choose a good way to search first - perhaps simple vowel/consonant rules, perhaps something more sophisticated (digraph tables?). Promising an arbitrary dictionary would prevent that kind of thinking, especially if there's nothing to say that "XYQQZ" won't be in it. @Laikoni, could your concern be addressed by a rule to outlaw built-in dictionaries? ("You must use only the supplied dictionary", for example) \$\endgroup\$ Jan 18, 2018 at 14:42
  • \$\begingroup\$ I see your point and also like the idea to incentive some form of language processing. However banning built-in dictionaries comes with the general problem of banning built-ins, namely what counts as a built-in dictionary. Just from the top of my head, if the scoring is only about look-ups in a provided English dictionary and built-in dicts as well as adding a dict in to your code are a banned, how about assessing built-in texts to sample a rough dictionary? I know that some languages can asses their own documentation from within the language itself. \$\endgroup\$
    – Laikoni
    Jan 18, 2018 at 14:52
  • \$\begingroup\$ Altogether, it might be a good idea to make the score a weighted combination of code length and the number of lookups. \$\endgroup\$
    – Laikoni
    Jan 18, 2018 at 14:53
  • \$\begingroup\$ How would you define "dictionary lookup"? A program may "copy" the dictionary and count that as one dictionary lookup. A check whether a word is in the dictionary? /// Also for the problem of built-in dictionary the solution is really simple: scramble the letters, and use different languages, or just use a random dictionary. For example bunny with the scramble b->x, u->y, n->q, y->z may well become xyqqz, and of course it won't change the challenge. /// What if there is no solution? \$\endgroup\$
    – DELETE_ME
    Jan 20, 2018 at 4:48
  • \$\begingroup\$ The core question is essentially codegolf.stackexchange.com/q/2478/194 so as code-golf I would vote to close this as a dupe. But with the current rules (and in particular the requirement to produce the smallest sequence of steps) I'm not sure how viable the proposed scoring system is. Basically answers will have to be equivalent to A* and there aren't that many admissible heuristics. In particular, heuristics for whether something is a word or not would only meet spec if they encode the entire dictionary. \$\endgroup\$ Jan 20, 2018 at 9:07
  • \$\begingroup\$ Thanks @Peter and others. I didn't manage to find the code-golf version, so the link is useful. I obviously need to think a bit further about the rules and scoring (in fact, I posted to Sandbox hoping to garner further ideas). I'm starting to agree that the dictionary can be abstract if the answer is allowed to generate heuristics from it before processing inputs. If I get any better ideas, I'll come back to this and update it. \$\endgroup\$ Jan 22, 2018 at 8:47
  • \$\begingroup\$ The obvious way to address the A* issue is to not require it to be a shortest path, but then you have to balance path length vs dictionary queries in the score, which is going to be messy. \$\endgroup\$ Jan 22, 2018 at 18:32
  • \$\begingroup\$ About "dictionary lookup"... check if a word in the dictionary using a black-box function seems good enough. Hopefully it won't make programs take awfully long time to run. / Restrict to a-z? Adding Unicode would be impossible to guess. \$\endgroup\$
    – DELETE_ME
    Jan 23, 2018 at 7:34
1
\$\begingroup\$

Objective

Given a 2D array (of x by x size), write a program or function to alternatively shift elements of the array along the anti-diagonals. (anti-diagonals are right to left, top to bottom). (first anti-diagonal moves down second anti-diagonal moves up with elements wrapping when they reach the end of the anti-diagonal)

Example

a b c d
e f g h
i j k l
m n o p

Will become:

a e i g
b c j n
f m h o
d k l p

I will follow the tradition of selecting the shortest working code as the best answer

**edited for user202729 suggestion

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Should it be "antidiagonals"? \$\endgroup\$
    – DELETE_ME
    Jan 22, 2018 at 13:58
  • 1
    \$\begingroup\$ Dupe? \$\endgroup\$ Jan 23, 2018 at 8:22
  • \$\begingroup\$ @PeterTaylor im trying to shift the anti-diagonals not reverse them \$\endgroup\$ Jan 23, 2018 at 8:55
  • \$\begingroup\$ So is the question I linked. \$\endgroup\$ Jan 23, 2018 at 9:22
  • \$\begingroup\$ @PeterTaylor look at the 4x4 test case and compare it with mine. I have a different result for that case. I am asking people to shift the elements along the anti diagonals, not to rotate the anti diagonals themselves. \$\endgroup\$ Jan 23, 2018 at 9:39
  • 1
    \$\begingroup\$ Although the specification of this proposal is not especially clear, I think that the only difference is that the question I linked rotates all anti-diagonals in the same direction whereas this rotates them alternately in one direction and the other. \$\endgroup\$ Jan 23, 2018 at 12:18
  • \$\begingroup\$ @PeterTaylor i will again clarify i am not rotating them i am shifting them. for example if an anti diagonal was say - 1 2 3 4 5 6 my outcome would be: 6 1 2 3 4 5 (or 2 3 4 5 6 1 depending on which antidiagonal it was) instead of 6 5 4 3 2 1 (which is the rotation of that antidiagonal) \$\endgroup\$ Jan 23, 2018 at 12:27
  • 1
    \$\begingroup\$ Shifting and rotating are different words for the same thing: the only difference is that rotating makes it clearer that it wraps round rather than losing one element from one end and introducing a new one at the other end. You're thinking of reversal. \$\endgroup\$ Jan 23, 2018 at 12:38
  • \$\begingroup\$ @peter Taylor your right... I goofed up while matching the arrays thanks for the catch \$\endgroup\$ Jan 23, 2018 at 13:03
1
58 59
60
61 62
145

You must log in to answer this question.

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