Sandbox for Proposed Challenges

Question

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

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

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

Answer 1

Output the points of this twisting fractal

Challenge

Output the points (in order) for the following fractal of size n:

(The above example is for n = 4)

We begin with the Binary Sierpinski Triangle, which can be generated recursively, by a number of cellular automata (including Rule 90), and by Pascal's Triangle.

As a refresher, Pascal's triangle is:

   |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7| 
---+----+----+----+----+----+----+----+---+
 0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0|
 1 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0| 
 2 |  1 |  2 |  1 |  0 |  0 |  0 |  0 |  0|
 3 |  1 |  3 |  3 |  1 |  0 |  0 |  0 |  0|
 4 |  1 |  4 |  6 |  4 |  1 |  0 |  0 |  0|
 5 |  1 |  5 | 10 | 10 |  5 |  1 |  0 |  0|
 6 |  1 |  6 | 15 | 20 | 15 |  6 |  1 |  0|
 7 |  1 |  7 | 21 | 35 | 35 | 21 |  7 |  1|

Here rows are i, columns are j, and the values are i choose j.

Using Pascal's triangle, we replace each value with its remainder mod 2 to get:

   |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7| 
---+----+----+----+----+----+----+----+---+
 0 |  1 |  0 |  0 |  0 |  0 |  0 |  0 |  0|     O        
 1 |  1 |  1 |  0 |  0 |  0 |  0 |  0 |  0|     OO       
 2 |  1 |  0 |  1 |  0 |  0 |  0 |  0 |  0|     O O      
 3 |  1 |  1 |  1 |  1 |  0 |  0 |  0 |  0|     OOOO     
 4 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0|     O   O    
 5 |  1 |  1 |  0 |  0 |  1 |  1 |  0 |  0|     OO  OO   
 6 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |  0|     O O O O  
 7 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1|     OOOOOOOO 

With the result "plotted" to the right, the n = 1 iteration of the Sierpinski Triangle.

Now, to keep the "centers" well defined, we take the center of each triangle to be its NE corner like so:

'              ^
''             |
'*'            N 
''''       <--E W-->
'  *'          S
''  ''         |
'*' '*'        v
''''''''  

Here is pseudocode to generate the fractal:

fractal(n):
    position = nth center
    while SE possible:
        go SE
        mark position
    while not all full:
        if current level not full:
            rotate counterclockwise on current level
            mark position
        else:
            go NW until reach non-full level
            rotate counterclockwise on current level
            while SE possible:
                mark position
                go SE
    return marked positions

Here's what that looks like for n = 2:

 '                              
 ' '                            
 ' 12'                          
 ' ' ' '                        
 '      9'                      
 ' '     ' '                    
 ' 10'   ' 11'                  
 ' ' ' ' ' ' ' '                
 '               '              
 ' '             ' '            
 '  4'           '  8'          
 ' ' ' '         ' ' ' '        
 '      1'       '      5'      
 ' '     ' '     ' '     ' '    
 '  2'   '  3'   '  6'   '  7'  
 ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '

Giving the following points marked (in order):

[[3, 12], [1, 14], [5, 14], [1, 10], [11, 12], [9, 14], [13, 14], [9, 10], [3, 4], [1, 6], [5,6], [1,2]] 

Rules

• Entry may be either a function or full program.
• Input is a non-negative integer.
• Output is the (properly ordered) list of points for the fractal above.
• You may use something other than a list to output the results if it allows the easy reading of the points, in order. For example, newline separated is fine.
• Output must contain exactly (3^n - 3)/2 points.
• This is code golf so shortest wins!

Questions

• Is everything well defined?
• Should I reformat the ASCII triangles? Or even replace everything with images?

Test cases if anyone is interested or I post this.

This is a challenge that I enjoyed solving so I hope I can smooth out the corners relatively quickly.

code-golf fractal sequence

Answer 2

Replace magic numbers

Tags: code-gold string

Introduction

Magic numbers are a common problem in software development, since they tend to make software hard to maintain. Best practise is to use named constants instead of raw numbers in the source code. In this challenge you have to clean up some code that makes extensive use of magic numbers.

The Challenge

Given a piece of code, replace every number that is not 0, 1 or 2 with named constants. If you encounter a number that you already created a constant for, use the existing constant instead of adding another one. The replacement is done by replacing the number with an uppercase letter [A-Z] and prepending an assignment in the form of A=5 to the initial input.

Example

x=input()
if x == 2:
    print 42
elif x == 1337:
    print 666
print 42

becomes

C=666
B=1337
A=42
x=input()
if x == 2:
    print A
elif x == B:
    print C
print A

Notes

• The order of the assinments that get prepended to the input does not matter.
• The order of replacements does not matter as well. You don't have to replace the first magic number with an A for example.
• You may take the input as a list of strings instead of a multiline string.
• You will never have to use more than 26 constants.
• A number that has to be replaced matches the regex [0-9]{2,}|[3-9].

Rules

• Function or full program allowed.
• Default rules for input/output.
• Standard loopholes apply.
• This is code-golf, so lowest byte-count wins. Tiebreaker is earlier submission.

Happy Coding!

Answer 3

Word Squares

Create a function or program that given a list of words and size n as arguments or standard input, outputs a word square with dimensions n by n. The output can be either formatted in a similar shape to a word square, or as a list of the words used in order by rows from the top and then by columns from the right.

Explanation

Word squares are a grid of letters that form words when read horizontally and vertically. The size of the square refers to the number of letters in each word.

Example

This is a size 5 word square. The words formed by each row are heart, ember, abuse, resin, and trend. In this example, the same words are formed by each column, but this is not a necessary condition.

H E A R T
E M B E R
A B U S E
R E S I N
T R E N D

Another example is this word square with size 4. The words formed by each row in this case are different from the words formed by each column.

L A C K
I R O N
M E R E
B A K E

Rules

• This is code-golf so the shortest solution wins.
• Builtins that solve this and the standard loopholes are not allowed.
• The words must be from this dictionary. You can take the filename of the dictionary or the contents as input or as an argument. (Recommend a dictionary here that consists of only English alphabet letters, in all lowercase or all uppercase.)
• If no such word square can be found using the given dictionary, no output or a false (or falsey) value can be returned.

Test Case

n = 4, dictionary = ...
L A C K
I R O N
M E R E
B A K E
-- or --
LACK
IRON
MERE
BAKE
-- or --
["lack", "iron", "mere", "bake", "limb", "area", "cork", "knee"]
-- or --
[["lack", "iron", "mere", "bake"], ["limb", "area", "cork", "knee"]]
-- or --
Similar to the above but with swapped cases.
The case is not important as long as it remains consistent.

Answer 4

Draw the Cool S code-golf ascii-art

Given a number n≥3, print or output the Cool S made with n vertical bars. The outputs for 3,4,5,6 are:

  / \
 /   \
|  |  |
|  |  |
 \  \/
 /\  \
|  |  |
|  |  |
 \   /
  \ /

    /\
   /  \
  /    \
 /  /\  \
|  |  |  |
|  |  |  |
|  |  |  |
 \  \  \/
 /\  \  \
|  |  |  |
|  |  |  |
|  |  |  |
 \  \/  /
  \    /
   \  /
    \/

     / \
    /   \
   /     \
  /  / \  \
 /  /   \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \   /  /
  \  \ /  /
   \     /
    \   /
     \ /

       /\
      /  \
     /    \
    /  /\  \
   /  /  \  \
  /  /    \  \
 /  /  /\  \  \
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
 \  \  \  \  \/
 /\  \  \  \  \
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
 \  \  \/  /  /
  \  \    /  /
   \  \  /  /
    \  \/  /
     \    /
      \  /
       \/

Any invisible whitespace is optional (trailing spaces and trailing/leading newlines).

How to draw the Cool S

Draw the Cool S just like you've done since childhood, except the number of vertical bars can be more than 3.

• Draw two rows of vertical bars.
• Connect them with slanted lines, tucking away the two remaining bars.
• Pair of the bars with slanted lines at the top and bottom.

Here's how we do this for ASCII art. Let's look at n=5.

A row has n vertical bars with two spaces between them

|  |  |  |  |

Draw two groups of n-1 rows, leaving two empty lines between them

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

Connect each top bar to the bottom bar one position right with a slanted line of two \, then close off the two unused bars with a /.

|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

Complete the S on the top and bottom by drawing lines sloping inwards that meet at the center. When n is odd, a gap of one space is left and the center bar isn't used.

     / \
    /   \
   /     \
  /  / \  \
 /  /   \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \  \  \/
 /\  \  \  \
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
 \  \   /  /
  \  \ /  /
   \     /
    \   /
     \ /

---

Spun off from this Sandboxed challenge by Beta Decay.

Answer 5

Simultaneous variable updates

Suppose we have the following code snippet:

a = 2*b + c
b = a - b + c
c = a + 3*c

In most programming languages, the above three lines would execute one after the other. This means that the a on the second and third lines would refer to the updated value of a, rather than the value of a before this code block ran.

If we wanted to see how a, b, c actually changes as the result of running the above three lines, we'd have to substitute earlier variable updates into later expressions, like so:

a = 2*b + c
b = a - b + c = (2*b + c) - b + c = b + 2*c
c = a + 3*c   = (2*b + c) + 3*c   = 2*b + 4*c

Hence, the first code block is equivalent to the following in languages like Python, which support simultaneous variable updates:

a, b, c = 2*b + c, b + 2*c, 2*b + 4*c

We can rewrite the original code block and the updated code block in matrix form, like so:

[ 0  2  1 ]        [ 0  2  1 ]
[ 1 -1  1 ]   ->   [ 0  1  2 ]
[ 1  0  3 ]        [ 0  2  4 ]

For example, the second rows of the input/output matrices above refer to b = a - b + c and b = b + 2*c respectively. Expressing the update step in the latter, simultaneous form is useful since we can perform multiple updates very easily, using matrix exponentiation (which we will not do in this challenge).

Here's one more example, for clarity:

                                              Input matrix:
a = a - b + d                                 [  1 -1  0  1 ]
b = 2*b + c                                   [  0  2  1  0 ]
c = -2a - b + d                               [ -2 -1  0  1 ]
d = b + c                                     [  0  1  1  0 ]

                                              Output matrix:
a = a - b + d                                 [  1 -1  0  1 ]
b = 2*b + c                                   [  0  2  1  0 ]
c = -2*(a-b+d)-(2*b+c)+d = -2*a - c - d       [ -2  0 -1 -1 ]
d = (2*b+c)+(-2*a-c-d) = -2*a + 2*b - d       [ -2  2  0 -1 ]

The task

Given a square input matrix representing a sequence of variable updates one after the other, output the corresponding matrix which represents the variable updates being applied simultaneously.

You may write either a function or a full program. The exact input/output format is flexible, as long as rows are separated from other rows and individual matrix entries are distinguishable. You may assume that entries in the input/output are integers in the range [-127, 127], and that the matrix will be at least 2x2.

This is code-golf, so the goal is to reduce the number of bytes in your program as much as possible.

Test cases

TODO. Will contain:

• Several simple 2x2 examples
• The above examples, plus a few more 3x3 or 4x4s
• An example with input rows all zero
• An example with input columns all zero
• Large examples: dense 10x10, sparse 10x10

---

Questions for the sandbox

• Any potential of being a dupe?
• Any interesting test cases?

Answer 6

Do my algebra homework for me!

Inspired by a true story

Ugh, my maths teacher gave me so much homework on quadratics.

Two whole worksheets, filled with equations like Expand (x+1)(x-6) and Factorize x^2-2x+1. I already hate it.

Suddenly, a lightbulb appeared out of nowhere, and landed about five centimetres above my head.

A stroke of thought went through me: Why not write a piece of code down instead of all those stupid answers? It would save me tons of time!

So here's the task: Make an algebra solver for me! To save my hand from breaking, the code needs to be as short as possible.

Instructions:

• Given an input in the form expand/factorize equation, return the algebraic equation:
  • Expanded, if the keyword (the first word) is expand (e.g. expand (x+1)(x+6) would return x^2+7x+6), or
  • Factorized, if the keyword is factorize (e.g. factorize x^2+9x+14 would return (x+2)(x+7).
• The equation will be quadratic, in the form ax^2+bx+c or (x+d)(x+e) (a to e are all placeholders, while x is the variable - the variable can be any letter from a to z - so an equation like expand (a+3)(b+6) would still hold).
• With an expansion equation that contains two or more unknowns (e.g. expand (a+3)(b+6)), place the letters in the summands with two or more letters in alphabetical order, and place the remaining summands in alphabetical order (so the previous example would equal ab+6a+3b+18).

This is code-golf, so shortest code in bytes wins. Good luck!

Meta

• Any dupes?
• I probably need a better title. Any suggestions?

Answer 7

Capture the Flag

^{Do you ever wonder why we're here?}

Objective

Capture the enemy team's flag and return it to your base. The first team to 3 captures wins the round. The player with the most wins across all (number TBD) rounds wins the game.

Teams

There will be two teams each round. Teams will be randomly, evenly assigned to all submissions at the start of each round.

Playing

The game will be turn-based. At the start of each turn, each player will be given the current map. All players will move simultaneously. Players shall submit their move as a one or two character ASCII string, composed from the following options:

• First character: wait, move, stab (if not holding flag), drop (if holding flag), or pick-up (if standing on a flag)
• Second character: north, east, south, or west, or nothing if waiting, dropping, or picking-up

Moving a direction will result in the player moving one square in that direction if possible, otherwise standing still (for example, if the player is attempting to move into a wall, or into an occupied square). Stabbing in a direction will result in killing the player standing in the adjacent square in that direction, unless the player is a teammate (no teamkilling). Stabs are processed before moves each turn. Dropping the flag results in it being placed on the ground beneath the player. Drop, pick-up, and wait commands ignore the second character. Invalid commands are interpreted as waiting. Case is ignored, so W and w are the same command. Either team may pick up either flag.

If two or more players attempt to move onto the same square, one of the players will be randomly selected to successfully move, and the rest will not move.

If a player is killed, they will drop the flag they are holding (if they are holding one), and will respawn in 3 turns in an unoccupied square in their home base. If there is no unoccupied square in their home base, they will respawn in the nearest square to the base. Respawns happen after stabs, but before moves.

Inside each base, there will be a 5x5 square room, with doorways in the middle of each wall, and the team's flag in the center of the room. Players who spend 5 consecutive turns inside their team's flag room (this includes the 4 doorways), while no enemies are present in the flag room and they are not holding a flag, will be killed at the conclusion of the 5th turn, to discourage camping. Successfully placing the enemy's flag on top of your flag's stand (in the center of the room), either by dropping it or being killed on top of the flag stand, will result in a point being scored for your team and the enemy's flag immediately returning to their flag stand.

The Map

(work in progress)

The world map will be a single level (no upstairs or downstairs), represented as such:

# : wall, cannot be moved into
. : an empty space
F : the enemy team's flag
f : your flag
! : a flag stand (with no flag on it)
@ : you
$ : you, carrying the enemy flag
% : you, carrying your flag
p : one of your teammates
P : an enemy player
c : a teammate, carrying or standing on top of the enemy flag
C : an enemy player, carrying or standing on top of your flag
s : a teammate, carrying or standing on top of your flag
S : an enemy player, carrying or standing on top of the enemy flag

Here is an example map (the actual maps used in the tournament will be posted later):

####################################################
#..................................................#
#..###.###########.######........###......##########
#..#....................#..........................#
#..#.....###.###...................#######.........#
#..#.....#.....#........#..........................#
#..#.....#.....#........#...................#...#..#
#..#........f...........#..........................#
#........#.....#........#....#########.............#
#..#.....#.....#........#..........................#
#..#.....###.###........#......##################..#
#..#...............................................#
#..#.#################.............................#
#.........................###########.........###..#
#..................................................#
####################################...............#
####################################...............#
#..................................................#
#..................................................#
#...............####################################
#...............####################################
#..................................................#
#..###.........###########.........................#
#.............................#################.#..#
#...............................................#..#
#..##################......#........###.###.....#..#
#..........................#........#.....#.....#..#
#.............#########....#........#.....#........#
#..........................#...........F........#..#
#..#...#...................#........#.....#.....#..#
#..........................#........#.....#.....#..#
#.........#######...................###.###.....#..#
#..........................#....................#..#
##########......###........######.###########.###..#
#..................................................#
####################################################

Controller

The controller and an example map and player are located on the challenge's GitHub project. Once I finish the controller, I'll copy the program here.

Restrictions

• Bots must be fully deterministic. RNGs may not be used.
• Bots may be written in any language, so long as they support reading ASCII input from STDIN and writing ASCII output to STDOUT. Anything that is written to STDERR will be ignored.
• Bots' processes will be started at the beginning of each turn, and must output their command and terminate within the given 5 seconds.
• Each bot will be able to store up to 1 MiB (1024*1024 bytes) of data on disk per game, for saving any stateful data they desire. The name of the bot's data file will be passed as the first command line argument to the bot process. Should a bot write more than 1 MiB of data during a single game, data from the beginning of the file will be removed to append additional data to the end of the file. At the end of each game, the data files will be wiped.
• Any attempt to tinker with the controller, runtime or other submissions will be disqualified. All submissions should only work with the inputs and storage they are given.
• Bots should not be written to beat or support specific other bots.

king-of-the-hill game

Sandbox notes

Anything missing or unclear (other than the parts specifically marked as TBD)?

Answer 8

Primitive Pythagorean triples

Introduction

A Pythagorean triple is a tuple of three positive integers a, b and c so that a² + b² = c². One example of that is (3, 4, 5).
One subset of those are primitive Pythagorean triples which require a, b and c to also be coprimes, so their only common divisior is 1. One example is (5, 12, 13)

The Challenge

Given three numbers representing a triple, output a truthy value if there is a triple representation of them that form a primitive Pythagorean triple and a falsy value if not.

Test cases

Truthy

Coming Soon

Falsy

Coming soon

---

tags: code-golf primes number-theory

TODO

• What about zero as input?
• Test cases
• Example for the different triple configurations?
• What about builtins?
• More descriptive title

Answer 9

Join the dots without crossing the line

code-golf geometry

---

Given a collection of distinct points in the unit square, output the points in order. This can be any order such that a closed polygon formed by straight line segments joining each point to the next (and the last back to the first) has no two lines crossing.

Input

1. There will be between 4 and 255 points.

2. Each one is represented by an ordered pair (x, y)

3. The coordinates will have entries in the range [0, 1), that is 0 <= x < 1

4. Each entry may have up to 8 decimal places, so the range is 0 to 0.99999999.

5. You may choose to accept integers instead, in which case the range will be 0 to 99999999.

6. You may take input in any reasonable format. For example:

   • (0.1, 0.2), (0.3, 0.4), (0.5, 0.7)
   • 10000000 20000000 30000000 40000000 50000000 70000000

Output

The output format need not match the input format as long as both are unambiguous.

Impossible cases

The code does not need to work for impossible cases, such as all points being colinear. Neither does it need to report such cases - it can simply not work. Behaviour is undefined.

Random algorithms

Your code must be deterministic. That is, it must always give the same output for the same input. For this purpose, the same points in a different order will be counted as distinct inputs and need not have the same output.

You may use pseudo random number generators provided the output is still consistent. If this requires setting a seed, that seed must be zero.

Time limit

Your code does not have to be particularly efficient, but it must finish for the 255 point test case in under 5 minutes.

The requirement for the code to be deterministic is so that this time limit can be checked with a single run. If your random number generator of choice cannot give consistent behaviour by default, then you will need to seed it with zero. If a random number generator does not allow for seeding and does not give consistent behaviour then you may not use that generator.

Test cases

[ TO BE ADDED ]

Output verification snippet

[ TO BE ADDED ]

Scoring

This is code golf. Shortest code in bytes wins.

---

Note that this is not a Traveling Salesman Problem. There is no requirement for the tour to be short, only for it to be non-intersecting.

Answer 10

The Fast and The Fourier

code-golfrestricted-complexity

Implement the Discrete Fourier Transform (DFT) for a sequence of any length using a Fast Fourier Transform algorithm (FFT). This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input. A DFT has time complexity of O(n²) whereas a FFT has time complexity of O(n log n).

The algorithm will compute a result based on standard DFT in the forward direction. The input sequence has length n and consists of the complex values {x₀, x₁, ..., x_n-1}. The output sequence will have the same length and consists of {y₀, y₁, ..., y_n-1} is defined by the relation below.

Bluestein's algorithm

One algorithm that meets these requirements Bluestein's algorithm. It is a special case of the Chirp-Z transform and is able to compute the FFT for a sequence of any length n by transforming it in order to solve it as a cyclic convolution which can be solved with a time complexity of O(n log n).

Keep in mind that it is not required that you only use this algorithm in your implementation. If you know a better way, feel free to use it.

First, an identity is used to rewrite the initial DFT in a form where a convolution can easily be recognized.

You can obtain two sequences from this new form

which allow you to write the DFT as a convolution of two sequences.

Sample

Get the input
    x = [1, 2, 3, 4, 5]

Get the length of the input
    n = 5

Compute the 'a' sequence
    a = [1, 1.618 - 1.176j, -2.427 - 1.763j, 3.236 + 2.351j, -4.045 + 2.939j]

Compute the 'b' sequence
    b = [1, 0.809 + 0.588j, -0.809 + 0.588j, 0.809 - 0.588j, -0.809 - 0.588j]

Compute the convolution of 'a' and 'b' (using summation)
    y[0] = (a[0]*b[0] + a[1]*b[1] + a[2]*b[2] + a[3]*b[3] + a[4]*b[4]) / b[0]
         = 15 / 1 = 15

    y[1] = (a[1]*b[0] + a[0]*b[1] + a[2]*b[1] + a[3]*b[2] + a[4]*b[3]) / b[1]
         = (-4.045 + 1.314j) / (0.809 + 0.588j) = -2.5 + 3.441j

    y[2] = (a[2]*b[0] + a[1]*b[1] + a[3]*b[1] + a[0]*b[2] + a[4]*b[2]) / b[2]
         = (1.545 - 2.127j) / (-0.809 + 0.588j) = -2.5 + 0.813j

    y[3] = (a[3]*b[0] + a[2]*b[1] + a[4]*b[1] + a[1]*b[2] + a[0]*b[3]) / b[3]
         = (-2.5 + 0.813j) / (0.809 - 0.588j) = -2.5 - 0.813j

    y[4] = (a[4]*b[1] + a[3]*b[1] + a[2]*b[2] + a[1]*b[3] + a[0]*b[4]) / b[4]
         = 4.253j / (-0.809 - 0.588j) = -2.5 - 3.441j

The Fourier tranform of x
    y = [15, -2.5 + 3.441j, -2.5 + 0.813j, -2.5 - 0.813j, -2.5 - 3.441j]

Rules

• This is code-golf so the shortest solution wins.
• Builtins that compute FFT in forward or backward (also known as inverse) directions are not allowed.
• Builtins that compute the convolution are not allowed. (Most will have not been allowed by the previous rule as they use FFT internally.)
• Your solution must have time complexity of O(n log n) where n is the length of the input sequence.
• Floating-point inaccuracies will not be counted against you.

Test Cases

FFT([1, 1, 1, 1]) = [4, 0, 0, 0]
FFT([1, 0, 2, 0, 3, 0, 4, 0]) = [10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j]
FFT([1, 2, 3, 4, 5]) = [15, -2.5+3.44j, -2.5+0.81j, -2.5-0.81j, -2.5-3.44j]
FFT([5-3.28571j, -0.816474-0.837162j, 0.523306-0.303902j, 0.806172-3.69346j, -4.41953+2.59494j, -0.360252+2.59411j, 1.26678+2.93119j] = [2, -3j, 5, -7j, 11, -13j, 17]

Related

• Compute the Discrete Fourier Transform - This contains some implementations for the standard DFT algorithm which has time complexity O(n²). You'll want to understand how to implement this before trying FFT.
• Too Fast, Too Fourier: FFT Code Golf - This previous challenge is the precursor to the current challenge here. Before, you only had to consider sequences where the length n was a power of 2 which allowed for simpler recursive implementations. The difference here is that you now have to implement an FFT algorithm that will work for sequences with any length.

Answer 11

Language succession

answer-chaining string

Given two words (two strings of lowercase-only letters separated by a space) as input to a program P_X written in language X, output two programs in languages Y and Z such that program P_Y outputs the first word and program P_Z outputs the second word. You may output or return these results. These programs may be returned in any fashion as long as it is evident that there are two distinct programs, e.g. double newline, or an array containing the result, or even a fancy box.

Here's the catch: the next answer's language X must be either language Y or Z from a past answer that has not as of the answer been used as a language X. The resulting nodes Y and Z cannot be a language that has appeared yet.

For example, say the first answer is a program written in Java that outputs a programs in Python 2 and Whitespace. Then, the next answer would write a program in either Python 2 or Whitespace that outputs programs in languages different than Java, Whitespace, and Python 2. Let's say it outputs answers in Foo and C++. Then, the next answer must be written in Whitespace, Foo, or C++.

The same user, however, may not extend their own nodes. That is, the person who posted the Java answer in the above example may not extend in Python 2 or Whitespace. Also, no person can extend two nodes of the same answer. So, someone couldn't extend both the Python 2 answer and the Whitespace one.

Here are languages I consider the "same":

• Different versions of the same language. So, Python 2 is Python 3.
• Trivial derivatives of a language. Brainfuck syntax substitutions are not valid, say.

However, this does not mean that Python 2 can be exchanged for Python 3.

The next solution in the chain must use the same character set as the previous program P_X, adding or removing only 5 characters from that set. There is no restriction on the length of the set. Any characters may be added or removed from the set. Even if characters are not used in a submission, they still remain in the characters set until forcibly removed. (You may optionally substitute the characters with characters in another code page at the same place.) If you need an example, look below.

The winner of this challenge is the one with the last answer. I define "last answer" as the most recently posted answer on this challenge where after a period of seven days after the answer was posted, no new nodes have been extended. Feel free to continue extending nodes after the challenge has ended, but I will not revise the accepted answer. You may use languages made/updated after this challenge and still compete, but only if that language was not made/updated specifically for this challenge.

First post

(this will not be part of the resulting question)

I will start it off. Here's the answer markdown:

# J, initial answer

    split =: 3 : 0
     w1 =. > 0 { ;: y
     w2 =. > 1 { ;: y
     ('alert("' , w1, '")') ; ('print("', w2, ')"')
    )

Languages used:
 1. JavaScript
 2. Python 3

Character set used: `"'(),.0123:;=>aeilnprstwy{`, space, `\r`, and `\n`.

Code points used: `10 13 32 34 39 40 41 44 46 48 49 50 51 58 59 61 62 97 101 105 108 110 112 114 115 116 119 121 123`.

No differences, is initial answer.

Call it like `split 'multiple words'`. Output looks like this:

    +-----------------+--------------+
    |alert("multiple")|print("words")|
    +-----------------+--------------+

Answer format

Here's an example of the answer format to be used.

# Language, extends [language](link to post)

    program

Languages used:
  1. lang 1
  2. lang 2

Character set used: `characters`.

Code points used: `code points`.

Differences:
 * added "c"
 * removed " "

<extra info>

Also, please edit posts saying that one of your languages has been used, like so:

Languages used:
  1. lang 1 ([used](link to post))
  2. lang 2

Language Availability Snippet:

/* Configuration */

var QUESTION_ID = 47338; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var LANG_REG = /<h\d>\s*([^\n,]*[^\s,]),[^]*?Languages used:\n\s*1. ([^\n]*)\n\s*2. ([^\n]*)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var used = [];
  var available = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(LANG_REG);
    if (match)
      used.push({
        language: match[1],
        user: getAuthorName(a),
        link: a.share_link
      });
      available.push({
        language: match[2],
        link: a.share_link
      });
      available.push({
        language: match[3],
        link: a.share_link
      });
      
  });
  
  available.filter(function (a) {
      return used.map(function (b) {return b.language}).indexOf(a.language) + 1
  });
  
  used.sort(function (a, b) {
    if (a.language > b.language) return 1;
    if (a.language < b.language) return -1;
    return 0
  });
  available.sort(function (a, b) {
    if (a.language > b.language) return 1;
    if (a.language < b.language) return -1;
    return 0
  });

  used.forEach(function (a) {
    
    var used_lang = jQuery("#used-template").html();
    used_lang = used_lang.replace("{{LANGUAGE}}", a.language)
                   .replace("{{NAME}}", a.user)
                   .replace("{{LINK}}", a.link);
    used_lang = jQuery(used_lang);
    jQuery("#used").append(used_lang);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
  });
  
  available.forEach(function (a) {
    
    var avail_lang = jQuery("#available-template").html();
    avail_lang = avail_lang.replace("{{LANGUAGE}}", a.language)
                   .replace("{{LINK}}", a.link);
    avail_lang = jQuery(avail_lang);
    jQuery("#available").append(avail_lang);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
  });

}

body { text-align: left !important}

#used-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#available-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="avail-list">
  <h2>Available</h2>
  <table class="avail-list">
    <thead>
      <tr><td>Language</td><td>Link</td></tr>
    </thead>
    <tbody id="available">

    </tbody>
  </table>
</div>
<div id="used-list">
  <h2>Used</h2>
  <table class="used-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Link</td></tr>
    </thead>
    <tbody id="used">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="available-template">
    <tr><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="used-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

Answer 12

Xor A Rational Number

Background

Consider the fraction 3/5 in base 2:

0.10011001100110011001100110011...
\___/\__/
 (a)  (b)

It has a "regular" or non-repeating part (a) and a repeated part (b). Let's go ahead and shift it right by one bit and xor it with the original:

 x           = 0.10011001100110011001100110011...
(x >> 1)     = 0.01001100110011001100110011001...
(x >> a) ^ x = 0.11010101010101010101010101010...
               \__/\/
               (a) (b)

By examining the regular (a) and repeating (b) parts, we find that (x >> 1) ^ x = 5/6.

Input

• Two whole numbers 0 < x, y < 256 such that 0 < x/y < 1 and gcd(x, y) = 1
• Input can be through STDIN or function arguments
• Input passed in any simple format for two decimals is acceptable, e.g. x y, x\ny, (x,y), [x, y], x/y, x%y (Haskell)
• Input must be in base 10

Output

• The numerator and denominator of ((x/y) >> 1) ^ (x/y), in base 10, in any clear output format.

Rules

• The submission may be a function or full program
• The output fraction does not have to be in its most reduced form
• Builtins for rational number xor are not allowed
• Infinite precision rational number types are allowed
• This is code golf so shortest answer in bytes wins! (Tie break by first submission)

Test cases

More tests upon request or when this question is posted.

3/5 -> 5/6
1/2 -> 3/4
1/3 -> 4/6

Note:

I'm not entirely sure whether this has a more or less trivial solution...

This is code golf so shortest answer is bytes wins!

Answer 13

The Hanoi KoTH

The KoTH is like this:

Two stacks of height-8 towers are on either side of a total of 11 pegs, and are coloured red and blue.

(Like this: [["R8", "R7", "R6", "R5", "R4", "R3", "R2", "R1"], [], [], [], [], [], [], [], [], [], ["B8", "B7", "B6", "B5", "B4", "B3", "B2", "B1"]] - each array is a peg.)

The objective is to move your entire tower to the opposite side before your opponent does, Tower of Hanoi-style. Red has to move all of their blocks to where Blue's blocks are, and vice versa.

Rules:

• You may not place a block on top of a block that is of an equal or smaller size.
• You are only allowed to place a block on your "end tower" once your opponent has cleared away all their blocks.
• If there are no more "moves" for either side, then the game is a draw.
• There is a limit of 10,000 moves. If neither side completes their tower, then the game is a draw.
• If you complete your tower before your opponent does and before the 10,000 moves is over, then you have won.
• Invalid moves include:
  • Moving a block that is covered by other blocks
  • Moving a block onto a peg that contains smaller or equal-sized blocks than it
  • Doing "null" moves (moves that don't do anything).

Input:

Your input will consist of two numbers separated by a space.

The first number will be the starting peg. Pegs are zero-indexed (so the first peg is 0, and the last peg is 10).

The first number is valid only if the associated peg is not empty, and the block that's on the top of the peg is yours. Any other input is invalid, and your bot will be notified.

The second number will be the peg that your block is moving to. If the stack that the block is moving to is either:

• Empty, or
• Contains only larger blocks than the moving block

then the block can move. Otherwise, your bot will be notified that this is an invalid move.

Valid inputs (based on the starting position) would be:

• 0 4 (Moving the block on peg 0, which is R1, to peg 4)
• 0 3 (Moving the block on peg 0, which is R1, to peg 3)

Invalid inputs (again, based on the starting position) would be:

• 1 3 (Invalid because there are no blocks on peg 1)
• 10 3 (Invalid because the top block on peg 5, B1, is not yours)
• 0 0 (Invalid because that is a null move)

If 5 invalid inputs are committed by the bot in a row, that counts as an automatic loss.

Output

The program will output to the bot what the current situation is - it will output the eleven arrays, each separated with the / symbol.

So, the starting position is like this:

R8R7R6R5R4R3R2R1//////////B8B7B6B5B4B3B2B1 (the middle nine stacks are empty).

Point System:

• Win: 5 points
• Draw: -1 point (to discourage drawing)
• Loss: -5 points

I've made a small controller here.

META STUFF

• Is this challenge a dupe?
• Is there anything I can clarify?
• Can anyone help with the controller (i.e. fix it up, optimise the code)?
  • Issues with the code:
    • Doesn't work with external files.

Answer 14

Repetition

In a language called Repetition (something I just made up), there consists an infinite string of 12345678901234567890..., with 1234567890 repeating forever.

The following syntax is available to output numbers:

• +-*/: This inserts the operator into the string of repeating digits.
  • Examples:
    • + -> 1+2 = 3 (The + inserts a + between 1 and 2)
    • +* -> 1+2*3 = 1+6 = 7 (Same as above, except two operators are used now)
    • / -> 1/2 = 0 (Repetition uses integer division)
  • Each operator is inserted so that it has one digit to its left, unless there are ~'s (see below).
• c: Concatenates with the next digit in the string.
  • Examples:
    • c+ -> 12+3 = 15 (The c "continues" the 1 and concatenates it with the next digit, 2, to form 12)
    • +c -> 1+23 = 24
• (): Brackets for processing numbers.
  • Examples:
    • (c+)* -> (12+3)*4 = 15*4 = 60 (Repetition uses the order of operations)
    • (c+)/c -> (12+3)/45 = 15/45 = 0
• s: Skip a number.
  • s+ -> 2+3 = 5 (s skips 1)
  • csc -> 124 (s skips 3, and c concatenates 12 with 4)

In the examples above, only a finite amount of digits in the infinite string are used. The number of digits used is equivalent to number of operators, concats and skips + 1.

Your task is, when given a string of Repetition code, output the result.

Examples of input and output are:

++ -> 6
- -> -1
(-)* -> -3
cscc -> 1245

This is code golf, so shortest code in bytes wins!

Meta:

• Is this explained remotely well? Anything I need to clear up?
• Should this be a code golf or a metagolf challenge? I'm thinking of something like my previous challenge, There can be only 1!.

Answer 15

Make an un-polyglot-able language!

cops-and-robbers

The cops' task is to create a language that is as hard to polyglot as possible. However, when making a language, you must follow these rules:

• ASCII characters only.
• The language must fit our definition of programming language, i.e. it must be able to add two numbers together, and check, when given a numerical input, if a number is prime or not.
  • You must post the adder and prime checker (the full program) into your answer, and they must be at most 1kb in size.
• You must post your full interpreter into the answer as well.
• Also, give a run-down of what each command in your language is and how your language works in general.
• You must complete the robbers' task, which is to create a polyglot of your language and a language from this list that outputs "Hello, World!". It must not exceed 5kb.
  • If your language doesn't support ASCII output, you can write a program that outputs the ASCII character codes of each character of "Hello, World!".
• All four of the things above (interpreter, adder, prime checker and "Hello, World!" polyglot) MUST fit into your answer.
• After your challenge is Cracked, you must post your answer to the robbers' task.
• If your language has not been Cracked for over 7 days, then your language is Safe. You must put Safe in your header, and post your solution.

• Your language answer should look like this:

  # {language name}, {cracked/safe} (<- the "cracked/safe" is only to be used 
                                     when your lang is either cracked or safe)
  
  {language description}
  
  {full interpreter}
  
  {adder} (max 1kb)
  
  {primality checker} (max 1kb)
  
  {Hello World polyglot} (<- only posted if your lang is cracked or safe, max 5kb)
  

The robbers' task is to create a polyglot using any cops' language that outputs "Hello, World!".

• You must output the exact string "Hello, World!", nothing more and nothing less (except for leading and trailing linefeeds).
  • If the cop's language doesn't support ASCII output, you may output the ASCII character codes of "Hello, World!".
• You only need to support two languages: the cops' one and one from this list of common languages.
• The final polyglot must not exceed 5kb.

• Your answer should look like this:

  # {language name}, {original author}, {bytecount}
  
      {insert code here}
  
  {description of code}
  

• Post a comment on the (in the cops' thread) language that you Cracked, linking them to your answer.

The winner will be:

• (Cops) the safe language that has the lowest byte-count for the "Hello, World!" polyglot. It will be declared after 1 month.
• (Robbers) the person who has cracked the most languages.

In case the language list changes, the languages are:

Java, Python, PHP, C#, Javascript, C++, C, Objective C, R, Swift, Matlab,
Ruby, VBA, Visual Basic, Scala, Perl, Lua, Delphi, Go, Haskell, Rust

Meta:

• Is this challenge a dupe?
• Anything I can improve on?

Answer 16

The challenge is to write the fastest code possible for computing the permanent of a matrix.

The permanent of an n-by-n matrix A = (ai,j) is defined as

Here S_n represents the set of all permutations of [1, n].

As an example (from the wiki):

In this question matrices are all square and will only have the values -1 and 1 in them.

Examples

Input:

[[ 1 -1 -1  1]
 [-1 -1 -1  1]
 [-1  1 -1  1]
 [ 1 -1 -1  1]]

Permanent:

-4

Input:

[[-1 -1 -1 -1]
 [-1  1 -1 -1]
 [ 1 -1 -1 -1]
 [ 1 -1  1 -1]]

Permanent:

0

Input:

[[ 1 -1  1 -1 -1 -1 -1 -1]
 [-1 -1  1  1 -1  1  1 -1]
 [ 1 -1 -1 -1 -1  1  1  1]
 [-1 -1 -1  1 -1  1  1  1]
 [ 1 -1 -1  1  1  1  1 -1]
 [-1  1 -1  1 -1  1  1 -1]
 [ 1 -1  1 -1  1 -1  1 -1]
 [-1 -1  1 -1  1  1  1  1]]

Permanent:

192

The task

You should write code that, given an n by n matrix, outputs its permanent.

As I will need to test your code it would be helpful if you could give a simple way for me to give matrix as input to your code.

Be warned that the permanent can be large (the all 1s matrix is the extreme case).

Scores and ties

I will test your code on random +-1 matrices of increasing size and stop the first time your code takes more than 1 minute on my computer.

If two people get the same score then the winner is the one which is fastest for that value of n. If those are within 1 second of each other then it is the one posted first.

Languages and libraries

You can use any available language and libraries you like but no pre-existing function to compute the permanent. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.`

Reference implementations

There is already a codegolf question question with lots of code in different languages for computing the permanent. Mathematica and Maple also both have permanent implementations if you can access those.

My Machine The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250. This also means I need to be able to run your code.

Answer 17

This has been donated to the Secret Santa Sandbox if anyone wants to take up the mantle.

Crazy Librarian's Interesting Numbers Game

king-of-the-hill card-games

Phew, you just managed to finish your code for the Arithmetic Sequence of Primes, and everything went swimmingly for your Crazy Librarian boss. Indeed, the math teacher taught the librarian a new card game as thanks for the prime sequences. However, the librarian wants to beat the math teacher at their own game, and so you're enlisted (again) to assist.

The card game was described as a two-player variation of a trick-taking game called California Jack. Each player is dealt a particular suit of cards from a standard US 52-card deck, and this forms their hand. A third suit of the cards is randomly shuffled and placed face-down between the players as the trophy deck. The fourth suit is unused. Each round, the top of the trophy deck is flipped face-up, and the two players select a card (in secret) from their hand to be their bid for that round, and places it face-down in front of them. The players reveal their bid card, and the higher card (aces low) wins the trophy card. The trophy card goes into the winner's trophy pile, and the two bid cards are discarded. If the players both bid the same card, neither gets the trophy card, and it is discarded along with both bid cards. The winner after all 13 rounds is whoever has the most points in their trophy pile, with Jack=11, Queen=12, and King=13. Note that it is possible for the game to end in a draw (including a zero-point draw).

Since you really want to impress the Crazy Librarian, you've ... enlisted ... the help of some of your friends, and you're going to create a bracket royale to find the best playing algorithm, and use that so the librarian can show up the math teacher.

---

Questions for Meta

• Program I/O? I'm envisioning a stateful program that keeps track of its own cards, where each execution is a run of the game against an outside opponent -- e.g., each input is [W/L] T# that says whether the program Won or Lost the previous round, and what the current-round's Trophy card is. Then, the output would be what card it chooses to bid. Repeat 13 times. Could also do an interactive version, scraping STDOUT and setting STDIN?
• Example of a really simplistic algorithm (in pseudocode) -- return argv[1] -- this just bids the same as whatever the trophy card is.
• The programs could keep track of their opponent's total and their total, but the controller would have final say (obviously).
• I'm envisioning a double-bracket style, where each program is randomly seeded into the bracket. Best 3-of-5 games moves it to the next round, while the loser gets re-seeded into the loser's bracket and can re-win a chance for the final four.
• What am I missing?

Answer 18

Planting Sugarcane

In the game Minecraft the crop sugarcane can only be planted on a block that has water along one of its edges..

Task

Given a area what is the most efficient way to place water such that every tile in the area is next to (does not include diagonals) a water block. That is how do you place water to maximize the amount of sugarcane that can be grown in that area.

For example if you had a small plus:

http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

You could grow the most sugarcane if you put the water in the middle:

http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg

http://www.clipartkid.com/images/656/black-and-white-square-clip-art-8lblvX-clipart.jpg

Or If you had a three by three square:

http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

You could place six sugarcane:

Sometimes the best answer will still leave dirt patches.

For example:

http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg
http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

Is best tiled as:

http://3.bp.blogspot.com/-Qs0ZbaSy4KM/T6AuMiorc6I/AAAAAAAABOc/RpA3dZGicC8/s1600/minecraft_dirt.jpg

I/O

Standard I/O applies.

You may take in an area as either an ASCII diagram with two distinct characters, one representing a block that is in the space and one representing a block that is not or a two dimensional data structure of truthy and falsy values representing the space.

You may output either output a ASCII diagrams with two distinct characters one representing water, and one representing everything else or a two dimensional data structure with truthy and falsy values with the truthy values representing the location of water.

You must also output the number of sugarcanes that can be planted with the scheme described.

Scoring

This is code-golf you will be scored accordingly.

Answer 19

Will the snake bump into itself?

Given a string containing NESW characters, check if a snake will bump into itself if it moves like this:

The snake starts out with length 2.

For every character in the string:

• If the character is N, move the head of the snake up one.
• If the character is E, move the head of the snake right one.
• If the character is S, move the head of the snake down one.
• If the character is W, move the head of the snake left one.

The rest of the snake follows the path of the head of the snake.

The snake grows 1 unit longer every 2 moves.

Your task is to determine if the snake will bump into itself, and give a truthy or falsey value accordingly.

Truthy Inputs

NS
NWSSENW

Falsey Inputs

NNN
SS
NWNNNWWWSSS
NWNNEEEESSS

More test cases coming soon.

Answer 20

Implement the sin function.

For those unfamiliar with trignometry. The sin function is a mathematical wave function, it can be defined a number of ways, but the canonical definition, is that it is sin(x) gives the ratio of the opposite side of an angle of measure (X) to the hypotenuse of a right triangle

---

Your job is to implement a program or function, that receives an angle (x) in degrees or radians, and outputs sin(x) to an accuracy of +/- .001 for at least the 360 degree values on a circle (or their radian equivalents). You may also specify a range that has width of a minimum of 360 degrees (or 2 pi radians) and require inputs to be converted to an equivalent angle to fit within that range. See the following table for outputs (multiples of 15 degrees are provided). You may not rely on any inbuilt library for trig functions. (i.e return Math.sin(x) is forbidden, or cos(90-x) or something similar 1/sqrt(tan(x-pi/2)^2+1)).

---

(Degrees|Radians|Sin)

0|0.0|0.0
15|0.2617993877991494|0.25881904510252074
30|0.5235987755982988|0.49999999999999994
45|0.7853981633974483|0.7071067811865475
60|1.0471975511965976|0.8660254037844386
75|1.3089969389957472|0.9659258262890683
90|1.5707963267948966|1.0
105|1.8325957145940461|0.9659258262890683
120|2.0943951023931953|0.8660254037844387
135|2.356194490192345|0.7071067811865476
150|2.6179938779914944|0.49999999999999994
165|2.8797932657906435|0.258819045102521
180|3.141592653589793|1.2246467991473532E-16
195|3.4033920413889422|-0.25881904510252035
210|3.6651914291880923|-0.5000000000000001
225|3.9269908169872414|-0.7071067811865475
240|4.1887902047863905|-0.8660254037844385
255|4.4505895925855405|-0.9659258262890683
270|4.71238898038469|-1.0
285|4.974188368183839|-0.9659258262890684
300|5.235987755982989|-0.8660254037844386
315|5.497787143782138|-0.7071067811865477
330|5.759586531581287|-0.5000000000000004
345|6.021385919380437|-0.2588190451025207
360|6.283185307179586|-2.4492935982947064E-16

---

This is code-golf, but it aims to be a canonical list of trig function implementation in esolangs, especially those without a sin function built in. No answer may rely on a built in method.

Answer 21

Happy New Year, 2017

Your task is to write a complete program, that if started today (December 16th, 2016), will produce no output until it is New Year's Day in 2017 (January 1st, 2017, 12:00am). At this exact moment (in your computer's local time), it will inform the user "Happy New Year!". After this, it can either keep running forever (producing no output ever again), or exit. Starting the program after this time will produce no output ever. Informing the user can be done in any manner EXCEPT for printing to stdout, such as a GUI, spoken through the speakers, sending an email or a text to you, or any other reasonable way of informing the user that they are now in 2017.

code-golf

(Note for sandbox reviewers: the "today December 16th" part will be updated for whatever day it is when I post the challenge for real.)

Answer 22

Dot matrix number visualization

Your task is to make a program that takes a number as input and outputs it as a wall of characters with spaces. The digits should be written like this:

  1    222   333     4  55555  666  77777  888   999   000 
 11   2   2 3   3   44  5     6   6     7 8   8 9   9 0   0
1 1       2     3  4 4  5555  6        7  8   8 9   9 0  00
  1      2    33  4  4      5 6666    7    888   9999 0 0 0
  1     2       3 44444     5 6   6  7    8   8     9 00  0
  1    2    3   3    4  5   5 6   6  7    8   8 9   9 0   0
11111 22222  333     4   555   666   7     888   999   000  

Each digit is represented as a grid of 5x7 characters consisting of spaces and the digit itself. The number should be written like above with a vertical line of spaces separating the different digits.

The preformatted text above should be the output of a 1234567890 number input. If you guys like this challenge, I'll post an image that better visualizes how each number should be printed.

Lowest size program wins.

Edit: Added a picture to better illustrate the digits.

Answer 23

Powerful numbers integer math

Look at the number 81 expressed as the sum of distinct powers of the same base:

• 81 = 81 (well, duh)
• 81 = 80 + 1 (easy)
• 81 = 9*9
• 81 = 4*4*4 + 4*4 + 1
• 81 = 3*3*3*3
• 81 = 2*2*2*2*2*2 + 2*2*2*2 + 1 (if you thought that was obvious...)
• 81 = 1 + 1 + ... + 1 (yeah, yeah...)

As you can see, for N > 4, there are always 4 trivial bases: 1, 2, N-1 and N. Powerful numbers are those numbers which have at least one nontrivial base. Please write a program or function that, given a number N > 4, outputs a truthy or falsy value for whether a nontrivial base exists. The results for N up to 30 should be as follows:

(1  F)  16  T
(2  F)  17  T
(3  F)  18  F
(4  F)  19  F
 5  F   20  T
 6  F   21  T
 7  F   22  F
 8  F   23  F
 9  T   24  F
10  T   25  T
11  F   26  T
12  T   27  T
13  T   28  T
14  F   29  F
15  F   30  T

This is code-golf, so the shortest solution wins!

Answer 24

Does Mathematica Have a Builtin?

Mathematica has a lot of builtins.

Your task is to take in a question names and its tags; and to guess whether or not Mathematica has a builtin that solves that question.

Rules

• Your code must be less than 100 bytes long.

• You may use internet to access the Mathematica reference guide you may also use the internet to access the tag wikis. Standard loopholes apply to internet access.

• For this challenge we will consider a valid builtin to be a builtin that does most of the computation for the challenge. Extra bytes spent on trivialities like IO formatting will be ignored.

• You must output a truthy value if Mathematica has a builtin to solve that challenge and a falsy value otherwise.

• If Mathematica has a builtin and for some reason the challenge does not allow Mathematica to compete or bans builtins your program must still output truthy.

Scoring

This is a test-battery so you will be scored on the percentage questions here (This is currently a work in progress there will be more cases in the final question) that your program gets the correct answer on.

test-batterydecision-problem

Answer 25

Minimal QWERTY

The task -- to output the layout of a QWERTY keyboard:

QWERTYUIOP
ASDFGHJKL
ZXCVBNM

But, you will be scored based on the length of your code, and on the number of distinct characters in it.

Rules

1) The code must output the three lines of text above (or the text above with optional trailing newline)

2) Standard loophole restrictions apply

3) If the language contains predefined information about the QWERTY layout, you are not allowed to use that information.

Scoring

The score will be defined as [Length of the program in bytes]*[# of distinct characters in the program], with lowest score winning.

For example, the code

ABAB1212

would have score 8*4=32 since it has length 8, but only 4 distinct characters: AB12

And the code:

ABC!!!{{{

Would have score 9*5=45, since it has length 9, and 5 distinct characters: ABC!{

Answer 26

Mark Duplicates

Given a list of non-negative integers, find the values which are duplicates and mark their positions.

For example, given [1, 2, 3, 2, 1], the output could be [1, 1, 0, 1, 1] where each 1 signifies that the value at that position is duplicated elsewhere in the array and each 0 signifies that the value at that position is unique.

Your output may use either 0 and 1, boolean values for false and true, or any other two distinct values as long as you remain consistent.

This is code-golf so minimize the length of your code.

Test Cases

[] -> []
[5] -> [0]
[0, 1] -> [0, 0]
[2, 2] -> [1, 1]
[1, 2, 3, 2, 1] -> [1, 1, 0, 1, 1]
[6, 3, 6, 3, 5, 2, 3] -> [1, 1, 1, 1, 0, 0, 1]

Answer 27

This message is open for anyone to adopt and post to main. For more details, see the chat room or meta post.

Nonogram it

Nonograms are one of my favorite types of puzzles, but sometimes there are not enough of them to solve!

The challenge here is to write a program that would take an image and output the values for the columns and rows of the puzzle.

INPUT: black and white PNG on STDIN

OUTPUT: two lines with the values to create the puzzle. First line is the columns, second the rows. The format of both lines is: [a,b,c...],[d,...],... (lists of integers separated with commas delimited with [], with each list separated by commas, ending in a newline. No dangling commas allowed inside the lists or at line end)

The squares on the image should be of 5x5px. The thereshold for determining if a square is filled is if it has at least 30% black inside it.

(3 sample images will be added later)

---

I'm not sure about the scoring for this challenge, most likely it should be a code-golf.

Additional scoring criteria I can think of:

• allowing to enter square size or cols*rows of the puzzle.
• accepting non black and white images
• reading other image types
• providing a solver

Answer 28

ASKEY robbers

You are a robber in the ASCII world. ASCII lock-key work in similar fashion as the real-world: matching ridges. Your objective is to write a program which generates a duplicate key for the ASCII locks.

Example:

A Lock is given as:

   |\    |\         
 __| \___| \____             
|               | 
|_______________| 

Its key shall be something like:

 _______________
|   __     __   |
|  |  \   |  \  |  
|__|   \__|   \_|

The fit being something like:

 _______________
|   __     __   |
|  ||\\   ||\\  |
|__|| \\__|| \\_|
|               |
|_______________| 

SandBox

I think the fit is weird. It didn't go as I had imagined when I finished typing in the ASCII drawing.

Answer 29

Sandbox

This will be my first kolmogorov-complexity submission, does this question fall under that category?

Is the question clear enough?

Is it too trivial?

Problem

Given no input write a program or a function that outputs or returns the following string:

(<(<>(<>.(<>.<(<>.<>(<>.<>)<>.<>)>.<>).<>)<>)>)

Rules

• Shortest program wins.
• Trailing whitespace allowed.
• Trailing newlines allowed.
• Unused parameters for functions allowed.

Answer 30

When did I need to be born to celebrate a magic birthday?

I was born in 1984 and in 2016 I became 32 years old, which is 20 in base 16, what a coincidence!

Your task is, given the year of interest -say 2016- , to calculate the year I had to be born to be able to say In 2016 I have celebrated/I will celebrate my 20th birthday (in base 16).

1. take n-digit decimal number - the year xy.
2. Split it in half, if n is odd, the digit the middle is appended to number side.
3. Calculate the year I had to be born to be x base ys old in the year of xy.

Your code shall return Not-a-Number or error message if the decomposition cannot be resolved.

Walkthough:

>  foo(2016)
1: '2016' -> '20' '16'
2: 20 base 16 = 32
3: 2016-32 = 1984
>> 1984

> foo(445)
1: '445' ->'44' '5'
2: 44 base 5 = 24
3: 445-24 = 421
>> 421

>foo(7)
1: '7' -> '7' ''
Error, base not defined
>> nan

>foo(10)
1: '10' -> '1' '0'
Error, base 0 don't exist
>> nan

>foo(1805)
1: '1805'->'18' '5'
Syntax error
>> nan

Test cases:

 7    : nan/error
10    : nan/error
78    : 71
445   : 421 
1024  : 1000
1805  : nan/error
1936  : 1891
1984  : 1891
1999  : 1891
2016  : 1984
2015  : 1985
10002 : 9998
10912 : 10759
116015: 115769

Shortest answer in bytes wins. Standard loopholes apply.