572
\$\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

4643 Answers 4643

1
96 97
98
99 100
155
0
\$\begingroup\$

Spiral text

Write a function or program that given a text with one or more characters in it outputs the text as a square spiral. The first letter of the text must be the center of the spiral and then all the characters must follow a clockwise spiral pattern as follow, striping all white spaces:

           789[10]
           612[11]
           543[12]
              [13]

Example

Input: Hello World!
Output:

               ORLD
               WHE!
               OLL

The text could be any length. Please validate with the following texts:

Once upon a time

Expected output:

o   n   a   t
p   o   n   i
u   e   c   m
            e


Tyger Tyger, burning bright, In the forests of the night; 

Expected output:

g   h   t   ;           
i   i   g   h   t,  I   n
n   r   y   g   e   r   t
e   b   t   t   y   ,   h
h   g   r   e   g   b   e
t   n   i   n   r   u   f
f   o   t   s   e   r   o

The minimung length of the input text is one character.

Note: Somewhat similar to this question

\$\endgroup\$
6
  • \$\begingroup\$ Test cases are more useful if you also include the expected output. ;) \$\endgroup\$ Apr 29, 2016 at 9:16
  • \$\begingroup\$ @MartinBüttner yay! Doing that \$\endgroup\$
    – Averroes
    Apr 29, 2016 at 9:17
  • 1
    \$\begingroup\$ Also having to support the empty string seems like an annoying special case that isn't likely to add anything interesting to most answers, so I'd personally probably let the input have at least one character, but that's your call. \$\endgroup\$ Apr 29, 2016 at 9:18
  • \$\begingroup\$ When you say "somewhat similar": why should I not vote to close it as a duplicate? It seems that the only difference is a reflection in the leading diagonal, which I would class as trivial. \$\endgroup\$ Apr 29, 2016 at 11:55
  • \$\begingroup\$ @PeterTaylor First of all the other question doesn't have any answer and it is a bit old so maybe now this question can get a little more audience now. Secondly the other question add "The characters can spiral into previous characters" that this doesn't add to the specs so I think they are different questions. \$\endgroup\$
    – Averroes
    Apr 29, 2016 at 12:39
  • \$\begingroup\$ Ok, the other question is horrible. This is actually more like various spiralling numbers questions, with the main difference being that it spirals outwards rather than inwards. \$\endgroup\$ Apr 29, 2016 at 12:52
0
\$\begingroup\$

Is this a helpful starting layout?

My computer has a Patience-style card game installed on it. It takes two packs of cards, removes the Aces, shuffles them, and deals 8 cards.

In order to maintain my 100% perfect completion record, I want as helpful a starting layout as possible. Deuces are immediately playable, so they are helpful cards. However other cards can only be played on cards of descending rank and opposite colour, which means that cards of the same rank and colour unhelpfully clog up the layout.

The challenge is to write a program or function which accepts a string or list of eight cards and outputs a truthy or falsy value. Cards are identified by their rank, which is one of the characters 23456789TJQK, and their suit, which is one of the characters CDHS. (Note that using numbers 10-13 for the rank is not an acceptable input.) For a layout to be helpful there must be at least one Deuce of any rank, and (except Deuces) there must not be any pairs of cards with the same rank and colour. Examples:

4H7STHTD5C5D2HQS -> unhelpful because of two red Tens
TD8S4CKC4HKD5S5H -> unhelpful because of no Deuces
2H7SJH3S4HKS7H3H -> helpful layout

This is , so the shortest program wins.

\$\endgroup\$
3
  • \$\begingroup\$ At first I thought this was a request for help, not the setting for a problem. You'll want to add what those inputs mean, what "a helpful layout" means, in detail. \$\endgroup\$
    – Nic
    May 2, 2016 at 18:19
  • \$\begingroup\$ As I understand, this can be solved by checking if the string contains 2 and its chunks of two are distinct, which seems pretty straightforward. \$\endgroup\$
    – xnor
    May 3, 2016 at 11:46
  • \$\begingroup\$ @xnor Not quite distinct, since a) you have to ignore the chunks that contain 2 and b) H==D and S==C for the purposes of comparison. \$\endgroup\$
    – Neil
    May 3, 2016 at 11:57
0
\$\begingroup\$

Solve for the Operators

In this challenge, you will be given a bunch of numbers and an answer. Your job is to find a sequence of operators that will successfully solve this equation. Use the numbers in the order that they are given

Operators: +, -, *, /

For example,

Numbers given: 2, 6, 8, 4, 5

Answer: 9

2__3__8__4__5 = 9

The program should find which operators can be used in the blanks to make the equation true. Remember Order of Operations Matters (PEMDAS)

Output:

2*3-8/4+5 = 9

Only 1 solution is needed per problem

Rules

  1. No built-in math functions beyond operators.
  2. Must Follow Order of Operations
  3. Must give one correct output.
  4. Least Number of Bytes Wins.

Examples:

Numbers: 4, 4, 4, 4

Answer: 0

4 - 4 + 4 + 4 = 0

Numbers: 1, 8, 6, 4, 5, 2, 3, 3

Answer: -35

1*8+6-4*5*2-3*3 = -35

Numbers: 1, -2

Answer: 3

1--2 = 3
\$\endgroup\$
2
  • 2
    \$\begingroup\$ In many languages, this will just be "find the cartesian product of +-*/ repeated as many times as there are blanks with itself, insert them over the blanks and call eval". It's fine if you want that, but it seems somewhat, uh, boring? \$\endgroup\$ May 5, 2016 at 13:26
  • 1
    \$\begingroup\$ 4 - 4 + 4 + 4 = 8 \$\endgroup\$ May 5, 2016 at 13:30
0
\$\begingroup\$

Make a times table sheet

The challenge is to make an ascii art version of a times table sheet.

Look at the following:

times tables.

Your answer should have the same layout as this table:

  • You should not include the title or the footer or worry about colors. Black and white is fine.
  • The times tables lines in each box should be randomly ordered.
  • You should include all the horizontal and vertical lines in the image (except in the header and footer).
  • The equals signs should be aligned in each column as in the example above.
  • It should be in ASCII art.

I am not worried about the precise spacing as long as the layout is as specified.

\$\endgroup\$
2
  • \$\begingroup\$ no ascii art for me? \$\endgroup\$
    – Leaky Nun
    May 6, 2016 at 17:41
  • \$\begingroup\$ @KennyLau I could make it ASCII art if people love that. \$\endgroup\$
    – user9206
    May 6, 2016 at 18:22
0
\$\begingroup\$

Challenge

Create a factor tree from a number. A factor tree will take a number > 1, n, and find 2 numbers that multiply together to equal n that are greater than 1. Then, it will repeat for the factors until every section reaches a number that does. Then it will output the last numbers.

For example:

enter image description here

Examples:

Input: n = 20

Graph(This is not the output):

enter image description here

Output: 2x2x2x3

Input: n = 54

Output:2x3x3x3

Input: n = 72

Output: 3x3x2x2x2

Input: n = 2

Output: 2

Scoring

Shortest bytes wins.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ I think you mean a factor tree, not factorial. That is very different. \$\endgroup\$
    – Riker
    May 7, 2016 at 3:11
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ yes that is what i meant. Thank you \$\endgroup\$
    – JoshK
    May 7, 2016 at 3:18
  • \$\begingroup\$ Would it be more interesting if i had the output be the tree instead of the numbers? \$\endgroup\$
    – JoshK
    May 7, 2016 at 3:20
  • \$\begingroup\$ yeah, I think the numbers is probably a dupe. Plus, it would be more fun/hard. (hard isn't bad) \$\endgroup\$
    – Riker
    May 7, 2016 at 3:20
  • \$\begingroup\$ I recommend having output be a image/ascii art, though that needs more specifications. \$\endgroup\$
    – Riker
    May 8, 2016 at 20:31
  • \$\begingroup\$ As it stands, this is a duplicate of codegolf.stackexchange.com/questions/1979/factorize-me \$\endgroup\$
    – user45941
    May 13, 2016 at 5:27
0
\$\begingroup\$

Inverse Square Probability

It's a fairly well-known fact that the sum of the reciprocals of squares is equal to pi squared divided by 6. That is,

Basel Problem

This is the Basel problem and was solved by Euler in 1735. I was thinking about generating a random patchwork of squares and trying to decide how to weight the probabilities of different square sizes, when it occurred to me that I could use this fact and make the probability of choosing a square's size be the inverse of its size.

For instance, if I pick a random point on the interval [0..pi^2/6), then based on the point I pick, r, I can translate it to a square size in the following manner (all numbers rounded to 3 decimal places):

0     <= r < 1     => s = 1
1     <= r < 1.25  => s = 2
1.25  <= r < 1.361 => s = 3
1.361 <= r < 1.424 => s = 4
1.424 <= r < 1.464 => s = 5
...

Your program or function should work for any input within the limits of your language (for instance, floating point precision, lack of built-in bignum capabilities, etc). Input will always be 0 <= r < pi^2/6.

Test Cases

{to be added}
\$\endgroup\$
0
\$\begingroup\$

ASCII Hulls


Input

A string containing a rectangle made up of m rows of n characters, separated by newlines. Apart from an optional trailing newline (which you may choose), the string must contain nothing else.

All the characters will be printable ASCII (including space). So ASCII characters 32 to 176 inclusive.

The dimensions m and n will not be specified in the input. They will both be in the range 1 to 80 inclusive.

Output

A string containing the same rectangle but with the convex hull of each non-space character filled with that character, higher ASCII values overwriting lower ones.

Overwriting does not prevent a character from contributing to the convex hull. For each character, the convex hull is defined based on the locations of that character before any overwriting.

Details

The rectangle of characters forms a grid of m squares by n squares. The vertices of the convex hull for a given character are the centres of the squares containing that character (apart from any in the interior of the convex hull). All squares whose centre is on the convex hull or in its interior become that character (until any overwriting).

Outline showing convex hull Filled convex hull

Equivalently you can use the top left corner instead of the centre (or any other point in the square) provided it is consistent. This will give the same output.

Test cases

Input followed by output in a single code block

P    
   P
 P  

P    
 PPP
 P


C    C

      G    G
    C    C

   G    G

CCCCCC
  CCCCC
   CCCGGGGGG
    CGGGGGG
    GGGGGG
   GGGGGG


 W    Z
X      X


Y      Y
 W    Z

 W    Z
XXXXXXZX
 W    Z
 W    Z 
YYYYYYZY
 W    Z

Scoring

The shortest code in bytes wins.

\$\endgroup\$
9
  • \$\begingroup\$ I don't understand what the "convex hull" is here. Could you give an example? \$\endgroup\$ May 10, 2016 at 21:55
  • \$\begingroup\$ @NathanMerrill It's a convex hull I think. \$\endgroup\$
    – Nic
    May 10, 2016 at 22:02
  • \$\begingroup\$ @NathanMerrill I added some test cases to visualise it \$\endgroup\$ May 10, 2016 at 22:08
  • \$\begingroup\$ @NathanMerrill I added a diagram which hopefully sums it up better \$\endgroup\$ May 10, 2016 at 22:52
  • \$\begingroup\$ How do you decide if a letter is within the hull? For example, it seems like the first should be P / PPPP / _PP, because part of the square between the midpoints of each letter is crossed. \$\endgroup\$
    – Nic
    May 10, 2016 at 23:11
  • \$\begingroup\$ @QPaysTaxes All squares whose centre is on the convex hull or in its interior become that character so it isn't enough for part of the square to be crossed - the centre of the square has to be on or within the convex hull. \$\endgroup\$ May 10, 2016 at 23:28
  • \$\begingroup\$ Oh, I see. That makes more sense.r \$\endgroup\$
    – Nic
    May 10, 2016 at 23:58
  • \$\begingroup\$ I'm having a bit of trouble deciding for this one, but apart from the fact that there's multiple hulls and ASCII parsing/writing involved, is the core of the challenge any different from existing convex hull challenges? \$\endgroup\$
    – Sp3000
    May 11, 2016 at 5:09
  • \$\begingroup\$ @Sp3000 unless the need to keep track of where the initial characters were while doing the overwriting for other characters adds anything in terms of golfing challenge, then I guess this is a duplicate \$\endgroup\$ May 11, 2016 at 14:35
0
\$\begingroup\$

Triangle Rasterization

I don't know if this is the right word for this, but here goes...

Given a triangle with a height and a width, you can convert it into squares by counting any square that the triangle occupies as a whole square. Your task is to calculate the area of this 'rasterized' triangle.

Your program should take two positive integers representing the height and width of a triangle and output the area of its 'rasterized' version. This should always be an integer.

No builtins are allowed, if there are any.

An example

What I'm actually talking about. This is a 6x4 triangle. The red area is the actual inside of the triangle, and the blue area is added on during the 'rasterization'. The total are of the red and the blue is 16. So, given 6 and 4 as inputs, your program must output 16, with or without a trailing newline.

Test cases

 input     output
 1, 1      1
 1, 2      2
 1, 3      3
 2, 2      3
 6, 4      16
 63, 47    1512

As you can probably tell, this is slightly larger than half the area of the enclosing rectangle, and gets more accurate for larger sizes.

Your program should preferably run in under a minute, but the answer with the shortest number of bytes will win.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Are you sure about the test case 63, 47? I make it 1535. \$\endgroup\$ May 12, 2016 at 22:16
  • \$\begingroup\$ @PeterTaylor while fiddling around with a solution I made, I think this error comes from rounding poorly. When I tried adding 1 to each column with a non-integer value and then flooring (I believe this is equivalent to taking the ceiling) I got your answer, but when I tried adding .5 to each value and then flooring I got the value the OP got. For reference: ceil and flop \$\endgroup\$ May 13, 2016 at 18:01
0
\$\begingroup\$

"45-degree rotation" of a square matrix


Introduction

Suppose we have a square matrix with odd sidelength, like this:

0 1 2 3 4
5 6 7 8 9
0 1 2 3 4
5 6 7 8 9
0 1 2 3 4

Let's divide it into nested layers as follows:

0 1 2 3 4
 +-----+
5|6 7 8|9
 | +-+ |
0|1|2|3|4
 | +-+ |
5|6 7 8|9
 +-----+
0 1 2 3 4

The nth layer, counting from the center, contains 8*(n-1) cells, and we rotate it n-1 steps in the clockwise direction:

0 5 0 1 2
 +-----+
5|1 6 7|3
 | +-+ |
0|6|2|8|4
 | +-+ |
1|7 8 3|9
 +-----+
2 3 4 9 4

Now our original matrix has been "rotated by 45 degrees", in a sense:

0 5 0 1 2
5 1 6 7 3
0 6 2 8 4
1 7 8 3 9
2 3 4 9 4

Namely, if this operation is applied twice, the result is a 90-degree rotation.

The task

Your input is an n×n matrix of single-digit integers, where n is odd, in any reasonable format. Your output is the 45-degree rotation of this matrix, as defined above.

Rules and scoring

You can write a full program or function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

[[3]] -> [[3]]
[[1,2,3],[4,5,6],[7,8,9]] -> [[4,1,2],[7,5,3],[8,9,6]]
[[0,1,2,3,4],[5,6,7,8,9],[0,1,2,3,4],[5,6,7,8,9],[0,1,2,3,4]] -> [[0,5,0,1,2],[5,1,6,7,3],[0,6,2,8,4],[1,7,8,3,9],[2,3,4,9,4]]
[[1,0,0,2,0,0,3],[0,1,0,2,0,3,0],[0,0,1,2,3,0,0],[4,4,4,5,0,0,0],[4,4,4,4,0,0,0],[4,4,4,4,0,6,7],[4,4,4,4,0,8,9]] -> [[4,0,0,1,0,0,2],[4,4,0,1,0,2,0],[4,4,4,1,2,0,0],[4,4,4,5,3,3,3],[4,4,4,0,0,0,0],[4,4,0,6,0,0,0],[4,0,8,9,7,0,0]]
\$\endgroup\$
0
\$\begingroup\$

KOTH Screeps Fighting AI

Screeps is an MMO for programmers (not a regular MMO, this is not modding, but rather the only way to play) where you program creeps. I want to make sure one more time: this is not hacking or modding, this is the only way you play the game. It has a builtin IDE that is always present.

This is your job: With 1550 energy, spawn an army of creeps to fight other player's armies. Your goal is to destroy the other team's spawn.

Specifications

  • Each team will start with 0 creeps and it's own spawn.
  • The team number will be hardcoded.
  • The spawns will be named Spawn1 and Spawn2, corresponding to each player's team
  • The room controller will be at level 8 and you will not have to worry about upgrading it.
  • Each creep will display an emoji chosen to represent it's team using creep.say(). This is so that members of the two teams can distinguished.

Rules

  • Not all creeps have to fight. Some can gather energy, build walls, etc.
  • Building structures is allowed. This includes walls, ramparts, towers, etc.

This is under construction! Please comment if you know how to improve this challenge!

\$\endgroup\$
1
  • \$\begingroup\$ I recall that in your purely energy gathering Screeps challenge, the example room could be used that did not require paying or creating an account. What is the situation with this new challenge? \$\endgroup\$ May 17, 2016 at 19:20
0
\$\begingroup\$

Serialize and Deserialize a Binary Tree!

A coding website, leetcode.com, has a method to serialize a binary tree.

Serialize means making a binary tree linear.

For example, we have:

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

    1
   / \
  2   3
     / \
    4   5

First, we fill the missing places with 0:

      1
     / \
    /   \
   /     \
  2       3
 / \     / \
0   0   4   5

Then read out all the lines from top to bottom:

->      1
       / \
      /   \
     /     \
->  2       3
   / \     / \
-> 0   0   4   5

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

Let's look at another example:

   1
    \
     2
    /
   3

Fill the missing places with 0:

   1
  / \
 0   2
    / \
   3   0

Note that 0 cannot have any child.

Therefore, this tree is serialized as [1,0,2,3,0].

Your task is to write two programs/functions, one to serialize, one to deserialize.

Specs

  • They may share code.
  • The binary tree will only contain positive integers.
  • A node in the binary tree is represented by [name,left_child,right_child].
  • You may not pre-fill the binary tree with 0s.
  • [1,0,2,3,0,0,0] is invalid.
  • Unlike the website given, [1,0,2,3] is invalid.

Notes

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

String covering

Given a target string and a list of fragment strings, determine whether the target string can be formed by concatenating fragments, allowing overlaps. Each fragment can be used any number of times.

Example:

cataract, [tar, car, tar, act, rat] -> True

cataract
cat
  tar
     act

Is this a dupe? It's hard to search for. Is it too similar to Imposters at the Zoo?

\$\endgroup\$
4
  • \$\begingroup\$ Related, related. \$\endgroup\$
    – Leaky Nun
    May 22, 2016 at 1:28
  • \$\begingroup\$ This challenge differs from zoo due to the fact that you can't "hide" mismatching parts, so I think it's fine. Not sure if there are any other potential dupes though. (also, I don't think Leaky's "related"s are that related) \$\endgroup\$
    – Sp3000
    May 22, 2016 at 4:25
  • \$\begingroup\$ Just to double check, does "Each fragment can be used any number of times." mean that cancan, [can] -> True? \$\endgroup\$
    – Sp3000
    May 22, 2016 at 6:45
  • \$\begingroup\$ I see a typo: "cat" isn't in the list but "tar" is twice \$\endgroup\$
    – user46167
    May 22, 2016 at 20:18
0
\$\begingroup\$

Primary Chances

Write a program that lists all possible outcomes for a general election with any number of candidates.

Rules:

  • Your answer must output how many states each candidate won in any format.
  • Candidates can have any name.
  • This is , so standard loopholes are forbidden, and shortest code wins.
\$\endgroup\$
0
\$\begingroup\$

Sort 2D points by Sierpiński curve order


[ WORK IN PROGRESS]


Input

A collection of distinct 2D points in the range [0,1] X [0,1].

Output

An ordered collection of the same 2D points, meeting the criteria for Sierpiński curve order.

Sierpiński curve order

  • The points are in the order that the Sierpiński curve would pass through them.
  • The order is cyclic - it does not matter which point is first.
  • The order may be clockwise or anticlockwise/counterclockwise, provided it is consistent.
  • The point at the centre of the range, (0.5, 0.5), may fall into any triangular quarter of the range, provided it is in the correct order among other points in that quarter. Similarly for all other points where both coordinates have finite binary expansion.

Although the curve is infinitely long and fills the unit square, it is arranged in a convenient shape that allows ordering points by calculating only a finite number of iterations. For example, if there are 4 points, one in each triangular quarter of the square, then they can be ordered based only on this information as the curve fills one triangular quarter before moving on to the next so the exact position without that quarter is not relevant.


Sandbox questions

  • Should ambiguous points be allowed to fall in any direction, or should I impose that they always fall left rather than right and up rather than down? Or just insist that the solution choose a consistent direction rule?
  • Can I assume that any three points that can be described by floating point variables can be ordered in a finite number of subdivisions? I'm pretty sure but welcome a counterexample.
\$\endgroup\$
0
\$\begingroup\$

Find ALL Longest Common Substrings

Unlike "Longest Common Substring" algorithm which returns just one string, or the length of it. This algorithm returns a score after taking all separate longest common substrings into account.

This program returns the score of how similar one string is to another according to the following rules:

  1. isolate only the longest (non-overlaping) matching substrings.
  2. score every longest substring found with this formula: (substring.length / ((string1.length + string2.length) / 2)) * substring.length
  3. sum the scores and return.

STEP 1 Example:

string1 = ABCD

string2 = ZBCA

Deconstructing string1: (list of substring in order)

ABCD

ABC

AB

A (also found in string2)

BCD

BC (also found in string2)

B (also found in string2 but ignored - part of a longer substring)

CD

C (also found in string2 but ignored - part of a longer substring)

D

Matches: A, BC

STEP 2 Example: (substring.length / ((string1.length + string2.length) / 2)) * substring.length

A: (1/((4+4)/2)) * 1 = .25

BC: (2/((4+4)/2)) * 2 = 1

Step 3 Example:

.25 + 1 = 1.25, Return 1.25

Here's an example of longer strings of variable length:

string1 = Approximate This

string2 = Appropriate That Thing

Matches: Appro, i, ate Th,  Thi

Appro: (5/((16+22)/2)) * 5 = 1.3157894736842105263157894736842

ate Th: (6/((16+22)/2)) * 6 = 1.8947368421052631578947368421053

i: (1/((16+22)/2)) * 1 = 0.05263157894736842105263157894737

 Thi: (4/((16+22)/2)) * 4 = 0.47368421052631578947368421052632

Return: 4.1052631578947368421052631578948
\$\endgroup\$
0
\$\begingroup\$

Fizzbuzz for tensorflow

Since I was a new and naive user, I posted this question. In one day it got over 25 upvotes but was shut down for being too broad. Clearly there is community interest -- so by the suggestion of @DrGreenEggsandHamDJ I'll try it again in the sandbox. I'd really like to see some of the answers here, so I appreciate any help you can give turning this question into a proper submission.

Original text copied below:


Inspired by the job-interview with Joel Grus, the goal of this challenge is to write a tensorflow (or other deep/machine learning) program that learns Fizzbuzz and correctly prints out the answers to the positive integers less than 1000.

You can assume there are files named train.csv and test.csv and each contain a sorted list of sequential integers and the fizzbuzz answer:

 ...
 100, buzz
 101, 101
 102, fizz
 103, 103
 104, 104
 105, buzz
 ...
 150000, fizzbuzz

test.csv spans 1-1000 and train.csv spans 1001-150000.

Rules

  1. You must not hard-code the rules to Fizzbuzz anywhere in your program. The output must be from a machine learned representation that is learned while running the code.
  2. You must utilize train.csv in the training set and check your output against test.csv. You cannot use test.csv during training.
  3. You must get all outputs correct from test.csv (but as is case with deep-learning, we'll allow your code to fail this rule no more than 5% of the time).
  4. You may use any language and any external module (eg. python/tensorflow) as long they explicitly perform some kind of learning. Reference both the language and the module in the title of your post.
  5. This is a popularity contest, so the submission with the most votes after one week wins.
\$\endgroup\$
5
  • \$\begingroup\$ What are the odds this will work well without an obscene number of iterations? A week doesn't seem like much time to test more than a single method or two. \$\endgroup\$
    – Geobits
    May 25, 2016 at 2:58
  • \$\begingroup\$ @geobits I'm not sure, but I can train a decent random forest model on Netflix predictions or a CNN to recognize basic images in about in hour. I figured the community would enjoy the challenge of a basic programming task in an unconventional manner. Surely fizzbuzz can't be that hard... \$\endgroup\$
    – Hooked
    May 25, 2016 at 3:05
  • \$\begingroup\$ Well, one problem that comes to mind immediately is that you need it to output valid code at all. So you're going to need to compile/run/whatever for every slight variation in the code. So then you need to figure out what building blocks you can give it to start with. A list of keywords to try, just random ascii, somewhere in between? That part in particular seems underspecified, but could make or break the odds of it working imo. \$\endgroup\$
    – Geobits
    May 25, 2016 at 3:08
  • 1
    \$\begingroup\$ I foresee arguments over where exactly the line falls for "hard-cod[ing] the rules to Fizzbuzz". \$\endgroup\$ May 25, 2016 at 11:45
  • \$\begingroup\$ Hmmm....if you come up with arbitrary rules of fizzbuzz (like different numbers, different amounts of numbers), that might work to prevent hardcoding. \$\endgroup\$ May 25, 2016 at 14:24
0
\$\begingroup\$

What can I build?

The Rules

Today I have decided to make geometric shapes out of toothpicks and gumdrops! However, I have a limited supply, so you have to figure out what I can build. I will give you an input in the format m n, where m is toothpicks (edges) and n is gumdrops (vertices.) Your output should be, in any output format of your choice, all 3D geometric shapes such that the amount of edges=m and the amount of vertices=n. The list of 3D geometric shapes you will use is this: Gist

  • You may NOT access the Internet.
  • No builtins relating to geometry or solids
  • This is code golf, so shortest code wins.
  • For no solids and invalid input, output nothing

Examples

In: 3 2 Out: <empty>
In: CodeGolf123 Out: <empty>
In: 12 6 Out (Bonus): {regular tetrahedron,unit equilateral square pyramid,unit equilateral triangular dipyramid,unit equilateral triangular prism,unit equilateral pentagonal pyramid,regular octahedron} Out (Regular): {regular octahedron} `

\$\endgroup\$
8
  • \$\begingroup\$ The first 3 rules can be deleted, as they're ppcg defaults \$\endgroup\$
    – Bálint
    May 22, 2016 at 20:03
  • \$\begingroup\$ Not the first... \$\endgroup\$
    – user46167
    May 22, 2016 at 20:04
  • \$\begingroup\$ I think this would work better with 1 solid with exactly n and m edges and sides. \$\endgroup\$
    – Riker
    May 22, 2016 at 20:29
  • \$\begingroup\$ How about doing that, but having this as a bonus? \$\endgroup\$
    – user46167
    May 22, 2016 at 20:37
  • 4
    \$\begingroup\$ 1. KISS. Ditch the stuff about the external file: the overhead to load it and the overhead generated by requiring it to be UTF-8 mean that no-one would want to use it anyway. 2. "No builtins" literally bans people from using any language. Specify what built-ins are banned. 3. Make the data available in a usable format: i.e. a text file hosted on gist.github.com or pastebin. 4. The bonus is a no-brainer: a 10% saving for changing two == to <=. Either make it compulsory or remove it entirely, because as it stands it's just complication. \$\endgroup\$ May 22, 2016 at 22:38
  • \$\begingroup\$ @petertaylor: I am currently on a phone so I can't put a gist... \$\endgroup\$
    – user46167
    May 23, 2016 at 10:42
  • 2
    \$\begingroup\$ There are a lot of shapes in that gist. Some of them are specified in different formats. If they're all to be supported it would be nice to have a standard format to represent them. Also some of these shapes specify different edge lengths. Will the challenge assume all edges are length 1 or will you potentially need to break toothpicks and keep track of the remaining pieces? \$\endgroup\$
    – Poke
    May 26, 2016 at 21:02
  • 1
    \$\begingroup\$ @Poke 1. Will fix 2. Irrelevant-- you have all sorts of toothpicks, some miniscule and others huge. \$\endgroup\$
    – user46167
    May 26, 2016 at 23:43
0
\$\begingroup\$

Code me music

Challenge

Write a program that will play music based on input.

Input

When your program is run it will be given a small song. Each note in the song will have 3 components:

[octave][pitch][duration]

where octave is the octave for the note to be played in, pitch is the key of the note (a b c d e f g), and duration is the length of the note in milliseconds. For example, 4c1000 would be middle c played for one second. Notes in a song are separated by spaces. Flats and sharps are possible, and they go after the note like this: 5gb1000 (5th octave g flat) for flats and 5g#1000 (5th octave g sharp) for sharps.

Output

Your program must produce sound based on the input. If one of the notes in the input is 3f500, your program must play f in the third octave for a half of a second.

Other notes

  • This is code golf, so shortest program in (insert period of time) wins.

  • No functions, only full programs.

  • The sound can be whatever you please.

  • Here are the frequencies of notes in the 4th octave in hertz:

    • 4c - 261.63
    • 4c#/4db - 277.18
    • 4d - 293.66
    • 4d#/4eb - 311.13
    • 4e - 329.63
    • 4f - 349.23
    • 4f#/4gb - 369.99
    • 4g - 392.00
    • 4g#/4ab - 415.30
    • 4a - 440.00
    • 4a#/4bb - 466.16
    • 4b - 493.88
  • A list of all frequencies is here.

Sandbox

  • Is the challenge objective clear?
  • This challenge may be hard for some languages, is that a problem?
  • Is this already a challenge?
  • Any positive feedback is welcome.
\$\endgroup\$
3
  • \$\begingroup\$ I think this could be improved by explaining what the frequencies are for the pitches at a given octave, and then explaining how an octave relates to that. That information is necessary to answer in any language which doesn't handle that itself, so I think it warrants being in the post rather than being behind a (potentially stale) link. In addition, you probably need to have some kind of leniency about frequency and duration, machines are not perfect after all. \$\endgroup\$ May 27, 2016 at 14:35
  • \$\begingroup\$ @FryAmTheEggman Thank you for your feedback, updated challenge. \$\endgroup\$
    – lapras
    May 27, 2016 at 14:54
  • \$\begingroup\$ Yes, this is already a challenge. (And, curiously, the second sandbox proposal which is a variant on that challenge in just a week). \$\endgroup\$ May 28, 2016 at 10:55
0
\$\begingroup\$

Plan a special tournament

tags: [more tags required]


I host a special tournament with any number n >= 2 of participants.

Here is a list of plans of tournaments for n = 2 to 20:

 2: 1) DE-2c-1w
 3: 1) RR-3c-1w
 4: 1) DE-4c-1w
 5: 1) RR-5c-2w 2) DE-2c-1w
 6: 1) RR-6c-3w 2) RR-3c-1w
 7: 1) RR-7c-3w 2) RR-3c-1w
 8: 1) DE-8c-1w
 9: 1) RR-9c-4w 2) DE-4c-1w
10: 1) RR-10c-5w 2) RR-5c-2w 3) DE-2c-1w
11: 1) RR-11c-5w 2) RR-5c-2w 3) DE-2c-1w
12: 1) RR-12c-6w 2) RR-6c-3w 3) RR-3c-1w
13: 1) RR-13c-6w 2) RR-6c-3w 3) RR-3c-1w
14: 1) RR-14c-7w 2) RR-7c-3w 3) RR-3c-1w
15: 1) RR-15c-7w 2) RR-7c-3w 3) RR-3c-1w
16: 1) DE-16c-1w
17: 1) RR-17c-8w 2) DE-8c-1w
18: 1) RR-18c-9w 2) RR-9c-4w 3) DE-4c-1w
19: 1) RR-19c-9w 2) RR-9c-4w 3) DE-4c-1w
20: 1) RR-20c-10w 2) RR-10c-5w 3) RR-5c-2w 4) DE-2c-1w

Explanation of the plan

  • The entire tournament enters the first round, which has c = n participants.
  • For each round:
    • If c is a power of 2, then this round will be a double elimination round, with 1 winner. After this round, the tournament ends.
    • Else, this round will be a round robin round, with floor(c/2) winners that continue to the next round.
      • If only one winner continues, the tournament ends.
      • Else, let c be the number of winners, and start again from "For each round".

The Challenge

Given n, return a plan of the special tournament with n participants.

This is a , so shortest code wins.

TODO: Reword the explanation clearly, write more content.

\$\endgroup\$
1
  • \$\begingroup\$ How does a round robin with five people work, where you have two winners? Most round robins would have a bye, so you'd end up with three winners continuing on. (same for any odd number) \$\endgroup\$
    – Geobits
    Jun 4, 2016 at 19:02
0
\$\begingroup\$

Golf a 2d maze (Yes, a whole game)

Nowadays, I am interested in making games. especially mazes. In this golf round of code, You should make a maze game. You can do it with just preset mazes, but, if you make it randomly generate, I will be a-maze-d and will give you bonus points.(Huh. is that a pun?) So, Go on, Why don't you try right now?

DETAILS:

  • Input W(Up), A(Left), S(Down), D(Right) until the player gets to the finish.
  • Display the maze and the player each input.
  • Move the player Up if the input is 'W', Down if 'S', Left if 'A', and Right if 'D'.
  • The Character for the wall and the player is undefined. you choose.
  • The Character for the wall, the player and the end square should be all different.

MAZE GENERATING:

  • You should get the Width and height in the input.
  • Not Necessary, but you can use Prim or Kruskal.
  • Also you can use the method mentioned in here.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ The spec as is probably has too many ambiguities, e.g. 1) What counts as a "maze"? 2) If I was to golf this question right now, I'd put the exit next to the player and make it so that the only valid move is into the exit. That would save a ton of bytes since I only have to check one input. 3) If random generation is optional, it's almost certain that it won't be done (but if you do make it mandatory, then you would need to specify what random generation means) 4) Do we have to handle invalid input from the user? \$\endgroup\$
    – Sp3000
    Jun 5, 2016 at 6:50
  • \$\begingroup\$ In order for this to fit as a challenge on this site, it needs to have a winning criterion. For example, code-golf (shortest code wins), or fastest-code. You can also use code-challenge if you define a score based on something else, but there must be some way of assigning a score to each solution so they can be put in order and encourage competition. \$\endgroup\$ Jun 6, 2016 at 13:52
  • \$\begingroup\$ I think this could be an interesting challenge, but it needs to be well defined before it will be ready. \$\endgroup\$ Jun 6, 2016 at 13:57
  • \$\begingroup\$ It is code-golf. \$\endgroup\$
    – user54200
    Jun 6, 2016 at 14:01
0
\$\begingroup\$

Light black box: generate mirror processors

[ WORK IN PROGRESS - LOTS OF OUTSTANDING QUESTIONS ]


Input

The list of black box output values for all black box input values from 0 to 255 (inclusive), in any reasonable format. Each value is also in the range 0 to 255.

Output

A text representation of a rectangular grid showing the locations and orientations of mirrors that will generate the appropriate black box output for each black box input.

Specification

  • The input bits arrive from the left of the grid, in the top 8 squares, initially travelling right.
  • The output bits depart from the right of the grid, in the top 8 squares, travelling right.
  • For both black box input and black box output, the most significant bit is at the top.
  • Bits move through the grid horizontally or vertically until they encounter a mirror or the edge of the grid.
  • Bits that leave the edge of the grid are lost.
  • A bit that would move onto a mirror at the next step instead changes direction by 90 degrees clockwise or anticlockwise according to the mirror type, and takes a step in that direction (a bit never stays on the same square).
  • If two or more bits arrive on the same square at the same timestep, all of them annihilate. Two bits can still pass through each other if this does not involve sharing a square (traveling in opposite directions, being adjacent facing towards each other on one step, and adjacent facing away from each other on the next).

Note that because a bit changes direction just before reaching a mirror, there cannot generally be a mirror in an input or output square, as this would prevent the bit entering/leaving by that square. However, a grid taking advantage of input/output that has no requirement for a given bit by placing a mirror that blocks a given input or output square is still valid provided it gives the correct behaviour.

Example

[ PENDING ]

Scoring

The score for each input is the area of the resulting grid. The total score will be the sum of the scores for each of the test inputs.


Sandbox questions

  • Is this too similar to domino circuits? The photons leave no trail so they can cross over their own and each other's paths arbitrarily many times. Also a given mirror can affect arbitrarily many photons, and each an arbitrary number of times.
  • Is this a duplicate of anything else?
  • Should the score be just the area of the grid, or also include the time between input and output? The time will have to be the worst case over all inputs, as reading the input before then would give a false result in some cases.
  • Should output bits have to arrive at the same time?
  • Should the time from input to output be required to be constant over all inputs?
  • There cannot be more output bits than input bits. Should test cases reflect this, or should a mechanism be introduced to make all patterns of output possible?
  • Should the particles be referred to as "bits", "photons", or something else?
  • Currently tie break is first posted. Should the number of mirrors be taken into account as a tie break first?
  • Should the grid wrap? I initially thought not, but then I realised there would need to be an extra row above the I/O rows to allow mirrors to redirect onto the top output bit. It might be simpler to keep to having the I/O rows at the very top, and simply put redirecting mirrors in the bottom row. This would make it possible to redirect onto rows 0 and 7 with only 8 rows in total.
  • I've chosen mirrors that change the bit's direction just before impact, rather than on impact. I liked the fact that this gives an asymmetry - reversing the direction will not reverse the route taken. This introduces the potential for sending a bit back along part of the same path without trivially sending it back to its origin. Is there any reason to stick to the symmetrical case instead?
  • The other thought that occurred to me was to have the mirrors change direction too, flipping between the two possibilities at each impact.
  • There are 256**256 possible ways to assign a value from 0 to 255 to each of 256 different inputs. This is far too large a space for hardcoding all solutions. However, this doesn't necessarily mean that the worst case grids will be huge. A lower bound on the worst case grid area is log(256**256,3), which is just over 1292 (since there are 3 possible states for each square). The maximal lower bound is likely to be far higher than that, but I have no idea how much higher. I'm likely to settle on a small enough space that code can be expected to deal with any input, but still a large enough space that hardcoding is impossible (I don't want to explicitly rule it out). (Here ** indicates exponentiation, as used in python.)
  • Mirrors that split bits, and bits annihilate on collision with each other. This will allow for arbitrary input and output rather than being restricted by the initial number of bits. I'm considering a number of possible approaches:
    1. One mirror type only: always splits a single bit into two bits in the two directions perpendicular to the current direction.
    2. 4 mirror types - each having a dead direction. A bit arriving from that direction is destroyed. A bit arriving from any other direction is split into two bits, one for each remaining direction.
    3. 4 mirror types - each having a dead direction. A bit is only split into two bits if the two perpendicular directions are not dead. Otherwise only one bit is produced, in the available perpendicular direction (or no bits if the bit approaches from the dead direction).
  • Can bits be left in the grid that do not terminate? Can a solution specify that the output should be measured at a set time, even if some bits will later reach the output squares altering the result? Should the output only be measured once all activity has ceased - excluding the possibility of using a repeating cycle?
\$\endgroup\$
0
\$\begingroup\$

Implement an HTTP Tunnel

I'm bored at work and stuck behind a draconian proxy.

They can take my other ports but they can never take my port 80 freedom!

Help me get all the internets!

This is a challenge.

requirements

  • a single web page that processes GET and POST data and produces output
  • if GET m=start
    • creates any files you feel are necessary (named pipes, scripts, what-have-you)
    • forks a process which will create a tcp connection
    • connects to host and port based on GET variables h and p
    • these variables should be cleansed so as not to allow command injection
  • if GET m=in
    • write the raw POST data to your forked process's tcp connection
  • if GET m=out
    • get all data available from the forked process's tcp connection and write as response
    • should always return right away (let's say, in less than 1 second)
  • if GET m=stop
    • kill your forked process
    • clean up any files it has created

Test data

my first instinct was to have this challenge be three separate pieces of code, a client which listens on a port locally and interacts with the web page, the web page itself, and a script which will be forked by the web page. your score would be the sum of all their byte counts. i decided to remove the last as the start process would likely have to create other files so why not have it create the script to run as well, and decided to remove the first option as well to make it nice and even.

is this a feasible challenge? i will add more explanations and test data soon i think. adding my own client would probably be helpful

\$\endgroup\$
2
  • \$\begingroup\$ HTTP is stateless, so this is a fundamentally broken way of designing a tunnel over it. I can't remember the exact headers, but there are ways in HTTP/1.1 of reusing a single connection for multiple bidirectional data transfers, and that would be the correct way of doing it. \$\endgroup\$ Jun 7, 2016 at 11:02
  • \$\begingroup\$ That's why the "start" mode is going to have to fork another process to handle the actual connection. I have this working with my php script forking a nc process which reads and writes from named pipes. I'll post it later. Sure you could use Connection: keep-alive but that connection usually times out pretty quickly, you'd have to implement your own pings to keep it alive, and there's no guarantee how long it would stay alive for. \$\endgroup\$
    – Nacht
    Jun 7, 2016 at 23:28
0
\$\begingroup\$

Code Golfed Rosetta Code Code Golfer

(any others? maybe , and/or )

Browsing examples on the Rosetta Code site, I can't help but think that all the code is just so long-winded, inefficient and ...well, readable. Something needs to be done.

Challenge

Choose a language, then write a function that takes the example source code, in the same language, for specific tasks on Rosetta Code and returns a golfed version of that code.

Winner is the person who can golf the example tasks the most. However, this is a code golf challenge so the length of your own source matters too.

Rules

  1. Write a function in your chosen language that takes a string as input and returns a string as output (or equivalent - reading/writing to stdio or file, etc is also ok)
  2. Input is the source code implementation, in your chosen language, of the following three specific tasks as shown on Rosetta Code (your function runs three times, once for each):
  3. Output is a code golfed version of the input with identical functionality (again in the same language)
  4. If there is more than one implementation of a task for a specific language, you must use the first listed
  5. If your chosen language doesn't have an implementation for one of the tasks, then you need to add it yourself (following the Rosetta Code rules - don't go messing up their site just to get a better score here)
  6. With the exception of the rule above, you may not, in any way, modify the content or order of examples on Rosetta Code
  7. You must leave the logical flow of the algorithm mostly intact (eg. you can't simply replace the J quick sort code with /:~)

Scoring

Score for each individual task is calculated as the output character count as a percentage of the input character count. Implementation score for your own code is simply its character count. Total score for a submission is the sum of the three task scores, plus the implementation score.

Submission with the lowest score wins.

So, assuming your function is 100 chars long and running it against the test tasks gives you the output counts shown, your overall score would be calculated as follows:

 Task      | Input char count | Output char count | Score
-----------+------------------+-------------------+--------
 Quicksort |            600   |            400    |  67%
 Happy Nos |            400   |            200    |  50%
 GCD       |            200   |            150    |  75%
--------------------------------------------------+--------
 Implementation score:                            |  100
--------------------------------------------------+--------
 Overall score:                                   |  292

Things I'm not sure about...

Before I post this as a challenge, it would be good to get input on a few things:

  • Will the "if your language doesn't have an implementation" rule cause problems, or can people be trusted to provide sensible implementations that follow the intent of Rosetta Code and don't simply artificially improve their score on the challenge? Is it better just to deny entries from languages which don't already have implementations?
  • With scoring, obviously it's a balancing act, a really terse language will likely get a solid "implementation" score, but should be less able to improve the length of the examples, whereas a verbose language will be the opposite. So, the having too few "tasks" included in the challenge will benefit terse languages, and too many will benefit verbose languages. I want to find a middle ground, so does three tasks seem reasonable?
  • Will someone just find an edge case language which has a really easily golf-able Rosetta example, that will make it unbeatable?
\$\endgroup\$
3
  • \$\begingroup\$ In the given example score, if an empty program echos then it would be better. More worryingly, this seems to allow coding to the test cases. Are the programs required to do something sensible with inputs other than the three test cases? \$\endgroup\$ Jun 9, 2016 at 9:42
  • \$\begingroup\$ @PeterTaylor - re: an empty program, I agree, this absolutely creates a minimum bar to beat, but even the most rudimentary whitespace stripping javascript function: (s) => {return s.replace(/[\s]{2,}/g,"");}; results in a score of 263, so my example score sheet is more the problem. \$\endgroup\$
    – Alconja
    Jun 9, 2016 at 11:09
  • \$\begingroup\$ @PeterTaylor - Re: coding to the tests, yes this is a bigger problem... The obvious solution is to simply include more tasks, since that would force people to target more generic things, rather than each individual task, but as stated the more you add the more you'll reward verbose languages (I think?)... One possible work around could be just to double things (i.e. have six tasks and make your implementation score, your code length x 2). \$\endgroup\$
    – Alconja
    Jun 9, 2016 at 11:11
0
\$\begingroup\$

Golf a golf-scoring program!

Given a space delimited array of integers, find the smallest number. It's that simple.

[Meta] This may in fact be a duplicate. Please tell me if so.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is basically a dupe of any regular sorting question, isn't it? Particularly something like Sign that word. \$\endgroup\$ Jun 9, 2016 at 12:52
0
\$\begingroup\$

Distance between two words

You are given an input of two strings consisting entirely of letter characters. The "distance" between two such strings is the number of operations from the following list that it takes in order to transform one word into the other:

  1. Adding a letter anywhere
  2. Removing a letter anywhere
  3. Changing a letter's case

Since your boss wants to avoid wear on the office keyboards as much as possible, you have to write a very short program to determine the distance between words so you can fix the typos.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Closely related. \$\endgroup\$
    – Leaky Nun
    Jun 10, 2016 at 13:56
  • \$\begingroup\$ Almost a duplicate of Leaky Nun's link. The only difference is that the linked challenge allows for straight substitution, whereas here it's two operations (a deletion and an insertion). \$\endgroup\$ Jun 10, 2016 at 13:59
  • \$\begingroup\$ Thanks guys, I had a brief look for dupes but couldn't find anything. If I come up with a good twist I'll edit the OP otherwise I suppose this is dead. \$\endgroup\$
    – A Simmons
    Jun 10, 2016 at 13:59
0
\$\begingroup\$

Cross Validated

(This challenge is almost complete, but something doesn't feel quite right)

Continuing the theme of using site names as challenges...

Your task

Write a program or function that accepts a string, and prints out the location, size, and validity of each cross in the string.

Definitions

  • Valid Cross- A cross where all four spokes of the cross are equal in length. The size of the cross is the number of segments of each cross.

Valid, size 0:

+

Valid, size 3:

   |
   |
   |
---+---
   |
   |
   |
  • Invalid cross- A cross where one or more spoke is a different length. The size is the number of segments of the longest spoke.

Invalid, size 2:

 |
 |
-+--
 |

Invalid, size 6:

+------

Rules

  • Each input will have one or more crosses.
  • The program should print out the location of the center of each cross. The location is zero-indexed and measured in characters/lines from the top left.
  • The size and validity, as defined above, of each cross should be printed out.
  • Each test case must pass without printing to STDERR.
  • Crosses will not overlap
  • Your program can take input via a string (with line breaks), an array of strings (each representing a line), or a 2d array of characters.
  • This is so shortest program, in bytes, wins

Test Cases

+ +-

(0,0) size 0, valid

(2,0) size 1, invalid

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

(3,3) size 3, valid

(9,5) size 4, invalid

(empty test case)

(must not crash or print to STDERR)

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

This question isn't fair.

I want you to tell me the chances of flipping an coin n times and ending up on tails.

Naturally this isn't a fair coin. In fact, it isn't even a standard unfair coin, where the chance of flipping tails is always p. This is a sticky coin, where the chance of the coin staying the same is p; the coin is fair at other times.

The coin starts off heads, so when n is 0 or p is 1 then the answer is always 0.

Your program or function should be capable of calculating the result to at least six significant digits.

This is , so the shortest program wins!

\$\endgroup\$
9
  • \$\begingroup\$ What does "the coin is fair at other times" mean? \$\endgroup\$
    – Leaky Nun
    Jun 16, 2016 at 13:12
  • \$\begingroup\$ @LeakyNun Sorry, I'm not sure what you're trying to ask there. A fair coin is one which is equally likely to produce heads or tails but there is no way of predicting which. This coin isn't always fair; a proportion of the time p it repeats the last result. \$\endgroup\$
    – Neil
    Jun 16, 2016 at 14:22
  • \$\begingroup\$ You said that the chance of the coin staying the same is p. Then, isn't the chance of it being different 1-p? So, do you mean that 1-p = 50%? \$\endgroup\$
    – Leaky Nun
    Jun 16, 2016 at 14:25
  • 1
    \$\begingroup\$ I think it means that the chance of the coin staying the same is p + (1-p)/2 and the chance of the coin changing is (1-p)/2. \$\endgroup\$
    – Emigna
    Jun 16, 2016 at 14:37
  • \$\begingroup\$ @LeakyNun Ah, sorry, the chance of it being sticky is p, and of being fair is ¬p. \$\endgroup\$
    – Neil
    Jun 16, 2016 at 15:24
  • \$\begingroup\$ Meaning, that the chance of it being the same is p+(1-p)/2 and the chance of it being different is (1-p)/2. What a meaningful obfuscation. \$\endgroup\$
    – Leaky Nun
    Jun 16, 2016 at 18:42
  • 2
    \$\begingroup\$ That means that the chance of it not changing is p + (1-p)/2 = (1+p)/2, and Sp3000's closed form needs changing to (1 - p^n)/2. It's still not exactly an interesting function to golf. \$\endgroup\$ Jun 16, 2016 at 18:43
  • \$\begingroup\$ I can see I should have described the coin of having a chance q of flipping, and you needed to calculate the probability of an odd number of flips in n trials. \$\endgroup\$
    – Neil
    Jun 16, 2016 at 18:53
  • \$\begingroup\$ (Removed my previous comment because I misunderstood and thought the probabilities were p and 1-p for same/change, but ditto Peter's comment) \$\endgroup\$
    – Sp3000
    Jun 16, 2016 at 22:59
0
\$\begingroup\$

"Optimize" a RegEx

Introduction

Inspired by atrociously large regex's like

/[0-9A-Za-z!@#$%&*()_\-+={[}\]|\:;"'<,>.?\/\\~`]+[0-9A-Za-z!@#$%&*()_\-+={[}\]|\:;"'<,>.?\/\\~`]*/g

I propose a challenge to create a string representing an optimized and sorted regex from an input string of characters expected to be matched.

Rules

  • only printable ASCII characters with code points 32 - 127 need to be supported:
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

The RegEx output string should:

  • Group 3 or more consecutive code points in the input string together like begin-end
  • Sort the characters and groups in order of ascending code point
  • Escape the literal character - to \- to differentiate it from a range

The RegEx output string should not:

  • Escape the characters !$()*+./=?[\]^{|}
  • Support any RegEx escape sequences like \w, \d or \s

Examples

Input:
helloworld
Output:
dehlorw

Input:
fedcabXZYVWU
Output:
U-Za-f

Input:
q0`p[|iOf(oc61TSr4dVwQ8m;%YDAPM*a/2j&h~u}
Output:
%&(*/-2468;ADMO-QSTVY[`acdfh-jmo-ruw|-~

Just so people can see what the last one's pattern is, here are the ASCII indices:

37,38,40,42,47-50,52,54,56,59,65,68,77,79-81,83,84,86,89,91,96,97,99,100,102,104-106,109,111-114,117,119,124-126

Spoiler Alert

Example implementation in JavaScript ES6:

f=s=>[...s] // spread string into array
  .sort() // sort array by ASCII indices
  .map(
    c=>c.charCodeAt() // convert each one to ASCII index
  ).reduce( // reduce sorted indices
    (p,c)=>(
      ~p[0][0]+c? // if last index is not one less than current index
        p.unshift([c]): // then start new run with this index
        p[0].unshift(c) // else continue existing run
      ,p
    ),
    [[]] // start reduce with empty run
  ).map( // map array of runs
    a=>(
      (
        a=a.map( // map each run
          n=>( // convert index back to ASCII
            c=String.fromCharCode(n),
            c=='-'? // if '-'
              '\-': // then escape it
              c
          )
        ),
        a.length>2? // if run has more than 2 indices
          [a[0],'-',a.pop()]: // keep only the begin and end
          a // else keep whole run
      ).reverse().join`` // reverse and join run
    )
  ).reverse().join`` // reverse and join array

\$\endgroup\$
4
  • 2
    \$\begingroup\$ This question seems to be about optimising regex character classes, not full regexes. Is that correct? \$\endgroup\$ Jun 17, 2016 at 19:46
  • \$\begingroup\$ @FryAmTheEggman I suppose you could say that. That's a more wordy title though so I just kept it simple. \$\endgroup\$ Jun 17, 2016 at 19:47
  • \$\begingroup\$ I could understand not requiring any escaping on the grounds that it's a minor detail. I could understand requiring enough escaping to make this actually a useful tool. But it seems really odd to require escaping - but not ]. \$\endgroup\$ Jun 17, 2016 at 22:07
  • \$\begingroup\$ @PeterTaylor I decided to escape only the characters that are necessary to determine whether an execution is correct or not. If you have an alternate suggestion, please feel free. \$\endgroup\$ Jun 18, 2016 at 1:53
0
\$\begingroup\$

Exercise your kids

I want you to output the nth verse of this kid's exercise song:

Head, and shoulders, knees and toes, knees and toes,
Head, and shoulders, knees and toes, knees and toes
And eyes and ears and mouth and nose,
Head, and shoulders, knees and toes, knees and toes.

Each verse is the same as the previous except that all occurrences of one word is masked by replacing it with a dash (you can use a two-byte dash of your choice) wherever it appears in the verse. The words are replaced in order however the word "and" is never replaced, therefore the next verse should look like this:

—, and shoulders, knees and toes, knees and toes,
—, and shoulders, knees and toes, knees and toes
And eyes and ears and mouth and nose,
—, and shoulders, knees and toes, knees and toes.

Also, the last verse should look like this:

—, and —, — and —, — and —,
—, and —, — and —, — and —
And — and — and — and —,
—, and —, — and —, — and —.

Your answer should specify whether n will range from 0 to 8 or 1 to 9.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Could you show us what the second verse would look like? \$\endgroup\$
    – Leaky Nun
    Jun 21, 2016 at 10:26
  • \$\begingroup\$ Although it can be deduced from the numbers, I'd recommend changing "one word is masked" to "all occurrences of one word are masked" to be explicit. \$\endgroup\$ Jun 21, 2016 at 10:32
  • \$\begingroup\$ Is this a challenge involving Unicode as the main topic? If not, can we replace (U+2014) by a simple hyphen - (U+002D)? \$\endgroup\$
    – Leaky Nun
    Jun 21, 2016 at 10:34
  • \$\begingroup\$ @LeakyNun No, but you may replace it with a double hyphen, as that's still 2 bytes. \$\endgroup\$
    – Neil
    Jun 21, 2016 at 10:38
  • \$\begingroup\$ Actually, it is 3 bytes. \$\endgroup\$
    – Leaky Nun
    Jun 21, 2016 at 11:05
  • \$\begingroup\$ Something to note is that "and" is the only word in the verse that starts with the letter "a". That means something like \b(?!a)\w+ will have its first match be the word to replace each time. Also, I don't believe any of the words are prefixes/postfixes of each other, so once you have them you can blindly replace all occurrences of them. This isn't a problem or anything, I just wanted to make sure you knew in case you wanted it to be harder. \$\endgroup\$ Jun 21, 2016 at 12:50
  • \$\begingroup\$ codegolf.stackexchange.com/q/100153/34718 \$\endgroup\$
    – mbomb007
    Nov 17, 2016 at 15:27
0
\$\begingroup\$

Calculate the Average Squared Error

Given a line y = mx + b and a set of n points (xi, yi), find the average square error between the given line and each set of points.

Formula

Your goal is to create a function or program that given the values m, b, and the set of points (xi, yi), outputs the average square error according to the formula above.

Rules

  • This is so the shortest solution wins.
  • Builtins that compute this value are not allowed. This includes builtins that compute a result which is a scaled value of this.
  • Floating-point inaccuracies will not be counted against you.

Test Cases

tba

\$\endgroup\$
1
96 97
98
99 100
155

You must log in to answer this question.

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