Sandbox for Proposed Challenges

Question

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".

Answer 1

Stego-nography: Hide A Stegosaurus with Steganography!

cops-and-robbers steganography ascii-art

This doesn't work as a cops and robbers challenge. Leaving for possible inspiration.

Making something that converts an image with a live dinosaur into one with a dead dinosaur would be a clone of Hiding information in Cats.

---

Cops

Devise a method for hiding this ASCII stegosaurus in an image.

                         .       .
                        / `.   .' "
                .---.  <    > <    >  .---.
                |    \  \ - ~ ~ - /  /    |
    _____          ..-~             ~-..-~
   |     |   \~~~\.'                    `./~~~/
  ---------   \__/                        \__/
 .'  O    \     /               /       \  "
(_____,    `._.'               |         }  \/~~~/
 `----.          /       }     |        /    \__/
       `-.      |       /      |       /      `. ,~~|
           ~-.__|      /_ - ~ ^|      /- _      `..-'
                |     /        |     /     ~-.     `-. _  _  _
                |_____|        |_____|         ~ - . _ _ _ _ _>

Source: custom 'cow' for cowsay

Create an encoder and a decoder. Post the decoder and two versions of three different images, each pair with and without the encoded stegosaurus. Include hashes for each of the six images.

Rules and Scoring

• The decoder must be able to decode any arbitrary ASCII text of at least the same size as the stegosaurus (either 677 characters or 14x63 characters if you assume the text is right-padded. Be consistent).
  • Only the part of the encoded message that actually includes the stegosaurus matters; extra bytes in the message can be ignored by the user or decoder, but must be either before/after the 677 characters or outside the 14x63 bounding rectangle, depending on how you encode it. (Sandbox: this phrasing is awkward)
  • In short, it must be possible for the robbers to kill your dinosaur (link to robber thread goes here) by replacing your stegosaurus with a dead one.
• You may not use asymmetric encryption in your solution. (For example, encrypting the stegosaurus with your private key before hiding it and then putting the public key in the decoder)
• You can use any lossless image format of your choice.
• You do not need to post the source code of your decoder. Precompiled Windows or Linux binaries are allowed, but must be packaged with all of their dependencies and be able to be run without any installation. Obfuscation and minification are allowed for interpreted languages and likewise should prepackage all third-party dependencies.
• You may not host your decoder on a webservice. The reason why is that it enables you to use symmetric encryption with no way to derive the key.
• As an objective criteria for the encoded images to be not easily distinguishable, the maximum absolute pixel difference between the images should be less than 4/255 for each color component in the entire image.

If at least one of your dinosaurs survives after one week, your dinosaurs are safe and you earn 10 points (after which point you can explain your algorithm). If your dinosaurs are all killed within a week, you score 1 point for each 24 hour period they survived.

The cop with the most points wins.

---

Robbers

You're a dinosaur hunter. The cops have hidden stegosauruses in three images. It's your job to find the stegos and kill them. You are to change the message hidden in each image from the original stegosaurus to this dead one:

                         .       .
                        / `.   .' "
                .---.  <    > <    >  .---.
                |    \  \ - ~ ~ - /  /    |
                   ..-~             ~-..-~
             \~~~\.'                    `./~~~/
              \__/                        \__/
                /               /       \  "
    _____     .'               |         }  \/~~~/
   |     |  .'   /       }     |        /    \__/
  --------''    |       /      |       /      `. ,~~|
 .'  X        __|      /_ - ~ ^|      /- _      `..-'
(_____     _-~  |     /        |     /     ~-.     `-. _  _  _
 `__U___--~     |_____|        |_____|         ~ - . _ _ _ _ _>

Cracking a cop submission requires that you kill all of its hidden dinosaurs. You earn a point for each submission you crack. Note that the cop can encode garbage or null data around the dinosaur (either by bounding box or before/after the 677 characters), but you do not need to leave this data untouched.

The robber with the most cracked submissions wins.

---

Sandbox

Does this work as a cops-and-robbers challenge? Any problematic loopholes or ways to abuse this?

Answer 2

Buddhabrot (speed edition)

Your goal is to generate an image like this one:

(Sandbox: this image will be replaced by a valid solution image for the challenge)

This is a render of a 2D histogram called Buddhabrot. The algorithm for generating it is very simple. If you have heard of (or written a program to generate) the Mandelbrot Set, this will feel familiar. The algorithm goes as follows:

1. Generate a random complex number \$z_0\$
2. Iteratively perform the calculation \$z_{i+1}=z_i^2+z_0\$. Do this \$N\$ times
3. Check if the absolute value of the number \$z_N\$ is larger than 3
4. If it is, calculate all the numbers \$z_i, 0 \leq i\leq N\$ again and map them to pixels.
5. For each pixel that is mapped to, add \$1\$ to the counter for that pixel
6. Repeat the 4 steps above a few million (or billion/trillion) times.

Since this algorithm depends on random sampling rather than just a single calculation for each pixel, it is not as easy to parallelize on a GPU. However, a GPU will still perform better than a CPU for this task. Since it is random, it is also dependent on having a large number of iterations to generate a smooth image. With a low number of iterations, the output image will be grainy.

To participate in this challenge, write a full program which creates a render of the Buddhabrot. For this challenge, the maximum iteration number is set to 100. That means that for every random complex \$z_0\$, you must write to the counter array if \$|z_{100}| > 3\$. Note that if \$|z_i| > 3\$ for some \$i < 100\$, then you can quit the calculation, since you know that \$|z_{100}| > 3\$.

If you want some help to get you started, I recently made an attempt to optimize this problem. You can read about my journey if you want.

Generating the image

A basic algorithm for rendering a Buddhabrot image is described above. To make it efficient, I would suggest that you use an unsigned int* to hold all the counters for the pixels. When running the program, you calculate which pixel should have its counter increased, then you add 1 to that index in the counter array. When you are done with the random number generation, you take your array of counters, divide every element by the array's maximum value. Then all values in the array will be in the range \$[0,1]\$. You can then use that value as the grayscale color of the corresponding pixel.

Specification

1. The output image must be exactly 1024x1024 pixels
2. The maximum iteration number is 100
3. The complex numbers must be sampled from the rectangle in the complex plane given by \$-2.5 < Re(z_0) < 1.5, -2 < Im(z_0) < 2\$ (Sandbox: these limits are subject to change). The sampling does not have to be uniform (you might discard points which you know are not important). However, it does need to result in a picture which is visually similar to the one in the post.
4. The output image must be a visualization of the area in the complex plane given by \$-2 < Re(z) < 2, -2 < Im(z) < 2\$ (Sandbox: these limits might change slightly)
5. You have 20 minutes to perform the sampling and generate the image. I will assist with tweaking to maximize your score.
6. You are free to use CUDA or OpenCL to generate the image. For any other methods of implementation, please include instructions on how yo get the environment ready.

Scoring

To ensure that we have an objective criteria for scoring, your score will be the total sum of all pixel counters. Since the Buddhabrot is a 2D histogram in its essence, this can be seen as the total number of samples. To be specific, you calculate your score before dividing by the maximum value and generating the image. The highest score wins. Note that if your approach is similar to mine, the theoretical maximum score is limited by the memory bandwidth. The bandwidth of my GPU is 484GB/s, and since each counter is 4 bytes, you can get 121 billion iterations per second. However, there might be more effective ways to save the samples using the CUDA caches, which could lead to higher performance than that. (Sandbox: I'm not 100% sure if my maximum speed calculation is valid)

Since I already have a working example for this problem, I have decided to add a further incentive. If your solution is 2x faster than my implementation, I'll reward 50 reputation once one month has passed from posting the question. If it is 5x faster, the reward goes up to 100 rep. If it is more than 10x faster, I'll award 150 rep. If you somehow manage to make your solution 30x faster, I'll throw in 200 rep. If multiple answers are eligible for the bonus, only the fastest one will be rewarded. If no answer is eligible for the bounty once one month has passed, the bounty will be rewarded to the first one who claims it. However, you can only claim one bounty, so if you have made your solution 5x faster but want to claim the 10x bounty, I will give you time to optimize your solution to reach the next bounty.

Testing machine

• Intel 5820K 6-core 12-thread CPU running at 4.4GHz
• 16GB DDR4 RAM
• NVIDIA GTX 1080Ti (11 GB GDDR5X, 3584 CUDA cores)
• CUDA 9.0 (I'll add information about C++ version and other relevant info)
• Windows 8.1 (sorry)

fastest-codemathcomplex-numbersfractalgraphical-output

For the sandbox

• Right now there are a few things that need to be clarified in the description.
• I will also update the post with an image that is 1024x1024 pixels. Is the question clear?
• Do I need to clarify anything besides the information that's left out right now?
• Is it okay to add reputation rewards from the start to attract answers?
• Are GPU challenges welcome? A short discussion about hardware was had in the chat, and I'm aware that not everyone has a NVIDIA GPU. That's why I made sure that there are OpenCL implementations of this problem.
• I say that the sampling should be uniform, but there have been some optimized solutions using importance sampling for this specific problem, should I allow that?

Answer 3

A Golden March

code-golfmatharithmeticfibonaccigeometrynumber

Draw a circle whose circumference is the golden mean. Choose a point and label it 1, then move clockwise around the circle in steps of arc length 1, labeling the points 2, 3, and so on. At each step, the difference between each pair of adjacent numbers on the circle is a Fibonacci number.

from Futility Closet.

Challenge

Given some natural number \$ n \geq 1 \$, determine the first \$n\$ points as described above. Then determine all differences between pairs of adjecent numbers and return them as a list.

Details

• The list should contain all the differences in the order in which they appear.
• It should start with the difference between \$1\$ and one of its adjecent neighbours. Then you need to continue recording the differences in the direction you started with.

Examples

to be determined.

Answer 4

Prime number construction game

Tags: code-golf

Inspired by this post, here is A "single player" version of the prime number construction game.

The game:

1. Start with a digit between 1 and 9.
2. Add a digit to the end, such that the resulting number is a prime number.
3. Repeat from step 2 until there are no more possible prime numbers.

The challenge:

Write a function (or required functions) that returns the sum of the lengths of the largest prime numbers you can get starting with each digit, following the game rules above.

The score:

Scoring will have two components:

1. The length of the code, in bytes (it's code-golf, after all), and
2. The sum of the length of the largest primes obtained, starting with each digit.

The total score will be the length of the code (1) minus the sum of the length of the largest primes obtained (2).

The lowest score wins.

Example:

Here's a code sample using R (verbose and non golfed):

isprime <- function(x) {
  for(i in 2:sqrt(x))
    if(x %% i == 0)
      return(FALSE)
  return(TRUE)
}

next_prime <- function(x) {
  for(i in sample(c(1,3,7,9))) {
    y <- strtoi(paste(c(x,i), collapse=''))
    if(isprime(y))
      return(y)
  }
  return(NULL)
}

longest_primes <- function(x) {
  primes <- 1:9
  for(d in 1:9) {
    y <- d
    while(!is.null(y)) {
      primes[d] <- y
      y <- next_prime(y)
    }
  }
  return(sum(nchar(primes)))
}

Here's a sample run of the code above:

 Digit | Largest prime obtained | Length
 ------+------------------------+-------
   1   | 19139                  | 5
   2   | 29399999               | 8 
   3   | 3797                   | 4
   4   | 4799                   | 4
   5   | 53                     | 2
   6   | 6173                   | 4
   7   | 719333                 | 6
   8   | 89                     | 2
   9   | 977                    | 3
 ------+------------------------+-------
 Total |                        | 38

Assuming the byte count of my code is 469, my final score is 469-38=431.

Posting your solution:

Please use the following header for your solution:
# [Language]: [Byte count] - [Sum of lengths] = [Total score].

Please include an explanation to your answer.

---

Miscelaneous:

I think this is a simple, yet fun, challenge. I've searched the site, and I haven't found a related challenge. If there's one, please point me.

I tried sometime ago to post a challenge, and I wasn't careful enough before posting (hence, I deleted it). I'd like to post a good first challenge. Any feedback will be appreciated.

Answer 5

Is it a D?

Given an image, check if it's a letter D.

Here D is defined as:

Let pixels labeled \$(x,y)\$ where larger \$x\$ mean at right and larger \$y\$ mean more up. If there exist \$x_0, x_1, f_0, f_1, f_2, f_3\$ such that:

• \$ (f \rightarrow (x\rightarrow f(x+1)-f(x)))^n (f_i) (x) >0\$ for \$n>0, 0\leq i<4\$
• \$ x_0<x_1\$
• Pixel \$(x,y)\$ is true iff \$y>f_0(x) \text{ and } y<-f_1(x) \text{ and } (y>-f_2(x) \text{ or } y<f_3(x) \text{ or } x_0\leq x<x_1)\$
• There should be a hole, i.e. a false pixel that can't reach border without acrossing a true pixel

Shortest code win. Don't mind if D doesn't follow the rule or a symbol which follows the rule doesn't look like a D at all

TODO: add test cases

Answer 6

There are 1000 phones in a city. Add some switches so that we can freely decide linking pairs (Any amount of pairs). Two phones are connected iff some closed switches directly or indirectly link them.

In graph-theoretic terms, phones and "new points" are vertices, switches/links are edges, and you need to construct a graph with least number of edges such that for all possible list of pairs of the "phone"-vertices, there exists a configuration of the switches (subgraph), such that vertices in the same pair are in the same connected component, and vice versa.

You need to answer with:

1. A list of links, where 0~999 are the 1000 phones, and 1000~ are just point.
2. A program that take some pairs of phone ids, where no two numbers are same, and output the switches that need to be closed. It should run on tio in 60s.

Fewest switches win.

A sample solution may be:

1. [(i,j) for i in range(1000) for j in range(1000,1500)]
2. def f(a):
     print ([(a[i][0],1000+i)for i in range(len(a))]+[(a[i][1],1000+i)for i in range(len(a))])

Which uses 500000 switches.

SN.

1. Should I require that when a connection is added or removed, there's a series of moves so that no other connections are affected?
2. Directly using sorting network for \$\mathcal O(n \log^2 n)\$ seems to use more switches than \$\mathcal O(n^2)\$ solution. Should I have more phones?

Answer 7

I'll Just Make A Snake

I noticed a post (now deleted) that pointed out that 05AB1E (legacy), when called with no arguments and non-empty input, will make a "snake" using the input:

Not sure what to do now with the input, so I'll just make a snake:


*****
    *
    *
    *
*****
*    
*    
*    
*    

Cute, and seems simple enough. However, the snake generation has a few quirks that I thought would make an interesting challenge to replicate.

The Challenge

When given a non-empty string as input, a snake is generated using the following algorithm:

1. If the input string is shorter than 17 characters, pad the string with duplicates of itself until its length is >= 17.
2. Generate a snake segment by replacing the non-space characters of the pattern with characters from the input string, following the direction of the snake. (Print characters right-to-left 5, up-to-down 3, left-to-right 5, up-to-down 4.)
3. If there is a previous snake segment generated, replace its last line with the first line of this segment.
4. Remove the used characters from the string.
5. Discard the first character of the remainder of the string. If there is no remainder, instead set the remainder to the original input string, minus its first character.
6. Pad the string with copied of the original input string until its length is >= 17.
7. Repeat steps 2-6 N times, where N = Length of input string.
8. Return the generated snake.

You do not have to handle empty inputs or non-string inputs.

You do not have to print the beginning message "Not sure what to do now with the input, so I'll just make a snake:".

Note: 05AB1E (legacy) actually has some different behavior when given a base-10 integer as input. We will be ignoring that and treating all inputs as strings.

General rules:

• Input and output may be in any reasonable format.
• Trailing spaces and/or a single trailing newline are acceptable.
• This is code-golf, so shortest answer in bytes for each language wins. No answer will be marked as the answer.
• Standard rules apply.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (i.e. TIO).
• Adding an explanation for your answer is highly recommended.

Test Cases

Here is an (ungolfed) Python 2 program which replicates this behavior, for clarity and generation of additional test cases.

pattern = """{0}{1}{2}{3}{4}\n    {5}\n    {6}\n    {7}\n{12}{11}{10}{9}{8}\n{13}\n{14}\n{15}\n{16}"""

def print_snake(in_str):
    print "Not sure what to do now with the input, so I'll just make a snake:\n\n"
    l = len(in_str)

    snek = [0]

    if l < 19:
        d,m = divmod(19, l)
        if m:
            d+=1
        in_str = in_str * d

    print_str, lost_char, rem = in_str, "", ""

    for i in range(l):
        print_str = rem + in_str
        print_str, lost_char, rem = print_str[:17], print_str[17], print_str[18:]
        snek.pop()
        snek += (pattern.format(*print_str)).split("\n")

    print "\n".join(snek)

Try it online!

Input: *

Output:
*****
    *
    *
    *
*****
*
*
*
*

Input: AB

Output:
ABABA
    B
    A
    B
ABABA
B
A
B
ABABA
    B
    A
    B
ABABA
B
A
B
A

Input: 123456789

Output:
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
12345
    6
    7
    8
43219
5
6
7
8

Input: sadness*and*despair

Output:
sadne
    s
    s
    *
d*dna
e
s
p
rsadn
    e
    s
    s
*dna*
d
e
s
irsad
    n
    e
    s
dna*s
*
d
e
airsa
    d
    n
    e
na*ss
d
*
d
pairs
    a
    d
    n
a*sse
n
d
*
spair
    s
    a
    d
*ssen
a
n
d
espai
    r
    s
    a
ssend
*
a
n
despa
    i
    r
    s
senda
s
*
a
*desp
    a
    i
    r
endas
s
s
*
d*des
    p
    a
    i
ndasr
e
s
s
nd*de
    s
    p
    a
dasri
n
e
s
and*d
    e
    s
    p
asria
d
n
e
*and*
    d
    e
    s
sriap
a
d
n
s*and
    *
    d
    e
riaps
s
a
d
ss*an
    d
    *
    d
iapse
r
s
a
ess*a
    n
    d
    *
apsed
i
r
s
ness*
    a
    n
    d
psed*
a
i
r
dness
    *
    a
    n
sed*d
p
a
i
adnes
    s
    *
    a
ed*dn
s
p
a
i

code-golf

Answer 8

What season is it?

I don't think we have a challenge for this yet, surprisingly. The closest ones are:

• What season is it? (bad, closed)
• Determine Season (only uses months)

Output the current season, using the astronomical definitions:

• Spring begins on the day of the spring equinox
• Summer begins on the summer solstice
• Fall begins on the fall equinox
• Winter begins on the winter solstice

You may use the northern or southern hemisphere dates.

Input

None (use the current date).

Output

One of these strings (case insensitive): spring, summer, fall (or autumn), winter.

Your program must finish in a reasonable (less than 1 day) amount of time.

---

Problems

• Is calculating the dates of the equinoxes/solstices too difficult? (I don't want the best solution to involve a big lookup table)

• What range of years should this be required to work in?

• Should the output format be less strict? ("Any 4 distinct values" rather than the season names)

Answer 9

Surreal Numbers

Surreal numbers are one way of describing numbers using sets. In this challenge you will determine the value of a surreal number.

Intro

A surreal number consists of two sets: a left and right. The value of the surreal number must be greater than all numbers in the left set and less than all numbers in the right set. We define 0 as having nothing in each set, which we write as {|}. Each surreal number also has a birth date. 0 is born on day 0. On each successive day, new surreal numbers are formed by taking the numbers formed on previous days and placing them in the left/right sets of a new number. For example, {0|} = 1 is born on day 1, and {|0} = -1 is also born on day 1.

To determine the value of a surreal number, we find the number "between" the left and right sets that was born earliest. As a general rule of thumb, numbers with lower powers of 2 in their denominator are born earlier. For example, the number {0|1} (which is born on day 2 by our rules) is equal to 1/2, since 1/2 has the lowest power of 2 in its denominator between 0 and 1. In addition, if the left set is empty, we take the largest possible value, and vice versa if the right set is empty. For example, {3|} = 4 and {|6} = 5.

Note that 4 and 5 are just symbols that represent the surreal number, which just happen to align with our rational numbers if we define operations in a certain way.

Some more examples:

{0, 1|} = {1|} = {-1, 1|} = 2
{0|3/4} = 1/2
{0|1/2} = 1/4
{0, 1/32, 1/16, 1/2 |} = 1

To the Sandbox: is this explanation clear? Anything I should add? I want to make sure of this before proposing the challenge.

Answer 10

Hearts king-of-the-hill

Goal: build the bot to play the classic card game Hearts.

The Rules

• Four players per game
• Played with a standard deck of 52 cards (in the protocol, 11 = J, 12 = Q, 13 = K, 14 = A)
• Object: finish the game with the least points
• Each game consists of many rounds, each of which consist of 13 tricks
• At the beginning of a round, each player is dealt 13 cards
• Then, each player passes three cards to an opponent:
  • Round 1: Pass to opponent 1 (to your left)
  • Round 2: Pass to opponent 2 (across the table)
  • Round 3: Pass to opponent 3 (to your right)
  • Round 4: No passing occurs
  • Round 5 is the same as round 1, and so on
• The player with the two of clubs plays it, beginning the first trick. The suit of the first card played in a trick is the "leading suit."
  • Each other player adds a card to the trick (clockwise). If they have any cards of the leading suit, they must play them; otherwise, they can play any card. (Exception: hearts and the queen of spades cannot be played in the first trick.)
  • The player who played the highest card in the leading suit takes the trick, adding its cards to their collection of taken cards (distinct from their hand)
  • The player who took the trick then begins the next trick with any card from their hand. (Exception: A player may not begin a trick with hearts until a heart or the queen of spades has already been played.)
• After 13 tricks, the round ends. Each player gains points for their taken cards:
  • 1 point per heart
  • 13 points for the queen of spades
  • 0 points for all other cards
  • Exception: If a player would gain 26 points (i.e. they took every heart and the queen of spades), every other player gains 26 points instead.
• Another round begins. This continues until a player has ≥100 points at the end of a round. At this point, the player with the lowest score wins (if there is a tie, extra rounds are played until there is no longer a tie).

The Protocol

Your program can be in any language (that I can run on macOS without too much fuss). It communicates using newline-separated JSON messages on stdin/stdout.

Messages your program receives:

• {"request": "pass", "direction": "left", "state": {...}} (other directions: right, across)
• {"request": "play", "state": {...}}

Expected responses:

• {"action": "pass", "cards": [{"suit": "hearts", "number": 14}, {"suit": "hearts", "number": 13}, {"suit": "hearts", "number": 12}]}
• {"action": "play", "card": {"suit": "hearts", "number": 14}}

The state object:

{
    "hand": [cards...],
    "taken": {playerId: [cards...]},
    "scores": {playerId: number}, // Does not include the current round
    "currentScores": {playerId: number}, // Points earned so far this round
    "tricks": [tricks...] // The current trick is the last object in this array.
}

The trick object:

{
    "leader": playerId, // The player who started the trick
    "leadSuit": "hearts", // or spades, clubs, diamonds
    "played": {playerId: card},
    "winner": playerId // Missing for the current trick
}

You always see the same player numbers: you are player 0, player 1 is to your left, player 2 is across from you, and player 3 is to your right.

Answer 11

Smallest Working Result - Referenced Reduction array-manipulation

RULES

1. Function must accept a keyed data structure
2. Function must return a modified version of that keyed data structure.
3. Function cannot use any libraries
4. Function will be tested against linked file.
5. Function must work against other similarly formatted files (no having a function that pops out a static answer!)

SCORING

1. To score, must be able to be run against multiple inputted keyed arrays.
2. To score, returned array must be able to be reverse-engineered into original array (conversion must be lossless).
3. Score will be determined by a keyed array built off of attached CSV (based off the oxford dictionary).
4. Score is to return an array with the fewest unique referenced keys.

DESCRIPTION

Build a function that does the following: It pulls in a keyed data structure (dictionary, keyed array, object, etc. depending on your languages' primary keyed reference structure) of the following structure...

ID   |  REF 1   |   REF 2   |   REF 3   | ...
1    |  
2    |   1      |   35      |   1
3    |   1      |   2       |   5       |
4    |   FOO    |   7       |   21      |
5    |   FOO    |   9       |           |   
6    |          |           |           |
7    |          |           |
BAR  |   6      |   6       |   6
8    |   BAR    |   BAR
...

Each object is made of and unrestricted number of references to other objects (that may or may not be in the table), or are 'prime' objects that reference nothing. Prime objects cannot be reduced. Objects that reference objects not in the table obviously cannot be fully reduced. Further, an object may not directly reference itself.

The goal is to have the fewest things referenced possible.

For example, a table like:

ID   |  REF 1   |   REF 2   |   REF 3   | ...
1    |   
2    |   1      |   1       |   7
3    |   1      |   2       |   1       |
4    |   3      |   1       |   3       |
5    |   1      |   3       |   3       |
6    |   1      |   4       |   FOO     |
7    |   

Could be reduced to:

ID   |  REF 1      |   REF 2                   |   REF 3     | ...
1    |  
2    |   1         |   1                       |   7
3    |   1         |   (1,1, 7)                |   1         |
4    | (1(1,1, 7)1)|   1                       |  (1(1,1,7)1)|
5    |   1         |  (1(1,1,7)1)              |  (1(1,1,7)1)|
6    |   1         |((1(1,1,7)1),1(1(1,1,7)1)) |   FOO       |
7    |   

(Notice, although the returned array is bigger and multidimensional, it actually has fewer references in it. While the first has 1, 2, 3, 4, 7, and FOO in the ref columns, the reduced table only has the unique values 1, 7, and FOO.)

The result is scored by the result that has the fewest unique items referenced while still being able to re-create the original table.

And to test, it's going to have a csv of the complete Oxford Dictionary thrown at it that's been converted to a keyed array. (I've uploaded a csv of it here: http://joshup.com/experiments/Oxford_English_Dictionary.csv, each word being the ID, and the following words being the references. Note, file is still being cleaned up, plan to clean before challenge gets moved from sandbox to main area.)

Although the examples are fairly straightforward, the code puzzler is reminded that this will be tested against an array built form the Oxford Dictionary using the word as the key, and the full description of the word as the array (each word being an array item, and, potentially a key somewhere else in the array). This means there is a very real chance that unlike the examples, arrays will reference eachother quite frequently, creating large loops of refrences between them, and the puzzle solver is reminded that choosing which key to reduce other keys into to will likely have a large impact on the final set of unique references.

Answer 12

IPv6 Aggregator

code-golf

The goal is to aggregate a list of ipv6 subnets into a smaller list.

Rules:

• The input is a list of ipv6 subnets in the extended format (such as 2001:0db8:0000:0000:0000:0000:0000:0000/48)
• The output must be the optimal
• The output list can be either in extended format, or using any valid compression
• The output list can be unsorted
• The value of irrelevant bits is not important (both ::1/127 and ::0/127 are considered valid)

Examples:

[2001:0db8:0001:0000:0000:0000:0000:0000/48,
2001:0db8:0000:0000:0000:0000:0000:0000/48,
2001:0db8:0000:000f:0000:0000:0000:0000/48,
2001:0db8:0000:000e:0000:0000:0000:0000/48]
will become
[2001:0db8:0000:0001:0000:0000:0000:0000/47,
2001:0db8:000e:0001:0000:0000:0000:0000/47]

Answer 13

Index and Get/Set Nested Arrays/Lists

This question is intended as extension of Home on the Range of Lists.

This challenge is to write one or two functions or a program which are getter and setter for a nested array/list mapped to 0-based or 1-based indexing.

Input

An array/list containing at least one nested array/list (length of 2) where each first element of successive nested arrays is set to either 0-based or 1-based indexes corresponding to each array. Each array is initialized with the first element set to the respective index of the full array.

Example

2 => [0, [1]]
     (0) (1) // 0-based indexing
6 => [0, [1, [2, [3, [4, [5]]]]]]
     (1) (2) (3) (4) (5) (6) // 1-based indexing

Rules

• If one function is used the second parameter must be the getter for the element value. If only two arguments are passed the function (input, index to get) acts as the getter. If three arguments are passed, the second argument acts as a getter and the third argument acts as a setter.

• If two functions are used one function acts as a getter exclusively and the second function acts as a setter exclusively. The first argument to the function is the index to get, the second argument is the value to set at the index passed at the first argument.

• If the array/list prototype is modified to chain the method to the rules above still apply.

• The functions are not expected to push to or splice from values in the input array/list.

Output

• Where a getter is used the value of that index of the array/list.

• Where a setter is used the complete array/list after setting the index to the passed value.

Test cases

(Single function acting as both getter and setter, where f is the single function)

Setter (0-based indexing)

f([0, [1]], 1, 7) => [0, [7]]

Setter (1-based indexing)

f([0, [1, [2, [3, [4, [5]]]]]], 6, 'map') => [0, [1, [2, [3, [4, ['map']]]]]]

Getter (1-based indexing)

f([0, [1, [2, [3, [4, ['map']]]]]], 6) => 'map'

(Two functions, get and set, 1-based indexing)

get([0, [1, [2, [3, [4, [5]]]]]], 4) => 3

set([0, [1, [2, [3, [4, [5]]]]]], 4, 'set') => [0, [1, [2, ['set', [4, [5]]]]]]

(Modifying Array (or equivalent in the language used prototype) 0-based indexing)

[0, [1, [2, [3, [4, [5]]]]]].get(4) => 4

[0, [1, [2, [3, [4, [5]]]]]].set(4, 'set') => [0, [1, [2, [3, ['set', [5]]]]]]

Winning criteria

Least amount of bytes in the language used.

---

Tags: 'code-golf' 'array-manipulation'

Answer 14

This is not the Timing Attack you are looking for!

code-golf cryptography

---

Introduction

I recently was writing a piece of code to verify a HMAC signature (to verify an API request). While doing that I found the given method in the documentation to be "incredibly verbose" and as a somewhat as a somewhat active PPCG member, that's obviously something that needs to be "fixed"! However being also an active member of Crypto.SE I know that HMAC tag verification needs to expose secret independent timing (a.k.a. "needs to be constant time") because otherwise an attacker may just brute-force a valid tag with a couple of dozen / hundred queries checking each time up to which byte was correct.

The input

The input is two strings a and b which are guaranteed to be of the same length and encoding.

The output

The output is a truthy or falsey value.

What to do?

You return a truthy output if a and b have the same content and a falsey value otherwise.

That sounds too easy, where's the catch!?

Your code must exhibit secret independent timing, that is the runtime of your code may not depend on the actual values of the two strings. To be valid your answer must provide a convincing argument that the execution time is independent of the secret values. To help you, I've listed a helpful guidelines:

• For secret-independent timing it is sufficient to use a non secret independent comparison on the HMAC of both strings under a fresh random key.
• For secret-independent timing there must not be early (loop-) returns or operations that are not evaluated due to short circuiting semantics (assuming you operate on the actual strings).
• For secret-independent timing the values must not be used as array indices or for similar lookups as timing variation can happen due to caching.
• For secret-independent timing the value must not contribute to control-flow decisions, e.g. as a condition for a while or if or as an operand to a short-circuiting &&.
• For secret-independent timing the value must not contribute to operands to multplication or division instructions.

Who wins?

This is code-golf so the shortest code in bytes per language that satisfies the I/O and the runtime behavior wins!

Answer 15

Restoration by patching code-golf statistics

Given a list of signed floating-point numbers and missing values denoted with a consistent value that doesn't represent a signed floating-point number of your language's natural signed float type (e.g. NaN, +∞, -∞, null/undefined/None, char, string, int/long, unsigned float, double, etc. as long as you can separate it from a real signed float), patch the list so that it only contains floats. Here's how you patch the list:

1. For each run of missing values:
   1. Take the mean of the value that precedes the run to the value that follows it.
   2. Patch the run:
      • If the run has an odd length, replace its middle element with that mean.
      • If the run has an even length, replace its two middle elements with that mean.
2. If there still are missing values, go to step 1.

The input denotes data points, and some of them are missing, so you want to patch them. Please note that this method of restoring lost stats isn't recommended for everything.

Your solution must not make use of some stuff.

Example: [1.0, _, _, _, 5.0, 6.0, 7.0, _, _, _, _, 12.0]

"Patch X.Y" represents the Yth patch of the Xth iteration of the method above.

Patch 1.1: [1.0, _, 3.0, _, 5.0, 6.0, 7.0, _, _, _, _, 12.0].
Patch 1.2: [1.0, _, 3.0, _, 5.0, 6.0, 7.0, _, 9.5, 9.5, _, 12.0].

Patch 2.1: [1.0, 2.0, 3.0, _, 5.0, 6.0, 7.0, _, 9.5, 9.5, _, 12.0].
Patch 2.2: [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, _, 9.5, 9.5, _, 12.0].
Patch 2.3: [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.25, 9.5, 9.5, _, 12.0].
Patch 2.4: [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.25, 9.5, 9.5, 10.75, 12.0].

Answer 16

Shenzhen I/O command encoder/decoder

The basic elements in Shenzhen I/O are:

P = p0 | p1
X = x0 | x1 | x2 | x3
R = acc | dat | P | X | null
L = 1 | 2 | 3 | ... | 15
V = R | -999 | -998 | -997 | ... | 998 | 999

acc | dat | X are registers containing number between -999 and 999, and P between 0 and 100, but you can't know them in advance. null is register that writing anything into it has no effect, and reading from it provides 0.

The command set is:

nop     nothing
mov V R R:=V
jmp L   unreplacable
slp V   sleep for max{V,0} seconds
slx X   unreplacable
add V   acc:=acc+V
sub V   acc:=acc-V
mul V   acc:=acc*V
not     unreplacable
dgt V   acc:=Tth decimal digit and sign if V in {0,1,2} else 0
dst V V set V1th decimal digit and sign to lowest digit and sign
    (negative/non-negative) of V2 if V1 in {0,1,2} else nothing
teq V V s:=1 if V1=V2 else s:=2
tgt V V s:=1 if V1>V2 else s:=2
tlt V V s:=1 if V1<V2 else s:=2
tcp V V s:=1 if V1>V2; s:=2 if V1<V2; s:=0 otherwise
gen P V V
        P:=100, sleep for max{V1,0} seconds,
        P:=0, sleep for max{V2,0} seconds

Only mov can take two same elements in P or X.

Now you're to encode each command into two bytes. If two commands do exactly same thing they are replacable, but:

1. If element(s) in P and X appear, the existance matters. E.g. mov acc null = nop, but dst 8 x1 = mov x1 null != nop

2. If multiple elements are in P and X, the order matters. E.g. teq acc p1 = teq p1 acc, but teq p1 p0 != teq p0 p1

3. Reading from P also writes 0 to P; Writing any negative to P equals to writing 0 to P, and writing number larger than 100 equals to writing one equal to 100. E.g. mov p1 null = mov 0 p1 = mov -43 p1

4. For sleep function we don't need to consider what happen after 1800 seconds. i.e. gen p0 900 901 = gen p0 900 900 != gen p0 900 899

You need to write an encoder(turning a command into 21 bits, or to say an integer between 0 and 2^21-1) and a decoder(vise versa). Smallest sum of length of encoder and decoder win.

A command checker and equivment finder(two equal commands are mapped to same one) is below: (Spoiler) (WIP)

alert('WIP');

<input id="vin" maxlength="20" onchange="foo()" onkeyup="foo()"><br><span id="vout">

code-golf encode

P.s. I changed the definition of L to allow single line command

Answer 17

Write a negadecimal number in words.

Negadecimal is a numeral system with digits \$0\$ to \$9\$ but is base \$-10\$ instead of \$10\$. Here are some examples (the left side is decimal numeral, and the right side is a negadecimal numeral):

$$ \begin{array}{rcrl} 0 & \to & 0 & \\ 1 & \to & 1 & \\ 9 & \to & 9 & \\ 10 & \to & 190 & \bigl(1 \cdot 100 + 9 \cdot (-10) + 0 \cdot 1 \bigr) \\ 11 & \to & 191 & \\ 20 & \to & 180 & \\ 99 & \to & 119 & \\ 100 & \to & 100 & \\ -1 & \to & 19 & \\ -9 & \to & 11 & \\ -10 & \to & 10 & \\ -11 & \to & 29 & \bigl(2 \cdot (-10) + 9 \cdot 1 \bigr) \end{array} $$

Basically, the carry rule (for both addition and subtraction) is that if you add one to nine, it wraps around to zero and you subtract one from the digit to the left, and if you subtract one from zero, it wraps around to nine, and you add one to the digit to the left. Also note that you can add or remove leading zeros from a number without changing its value. (In particular, the empty string represents the empty sum, i.e. zero.)

Challenge

Anyways, for the actual challenge, you will take an integer as input and convert it to negadecimal. Then you will convert that to words. What do I mean by that?

The digits \$0\$ to \$9\$ have their regulars names (i.e. zero, one, ..., nine). The negadecimal numbers \$10\$ through \$90\$ (i.e. negative ten through negative ninety) have the following names:

onetao, twotao, threetao, fourtao, fivetao, sixtao, seventao, eighttao, ninetao

The negadecimal numbers \$100\$ to \$900\$ have their regular names (i.e. one hundred, two hundred, ..., nine hundred).

Numbers that are a digit followed by three or more zeros are created by combining the above names. For example, negadecimal \$2000\$ is twotao hundred, \$40000\$ is four hundred hundred, \$300000\$ is threetao hundred hundred, etc.

All other numbers are named by writing it in expanded notation, naming each summand (which will be one of the above), and conjuncting them. For example, negadecimal \$5402=5000 + 400 + 0 + 2\$ is fivetao hundred, four hundred, and two.

Zero summands are a special case. If the whole number is zero, you just write zero. Otherwise, you omit all zero summands.

Examples

Here are some examples (the left side is a decimal numeral, and the right side is a negadecimal numeral noun):

0 → "zero"
10 → "one hundred and ninetao"
11 → "one hundred, ninetao, and one"
-11 → "twotao and nine"
-10 → "onetao"
-9 → "onetao and one"
101 → "one hundred and one"
999999997 → "ninetao hundred hundred hundred hundred, nine hundred hundred hundred hundred, ninetao hundred hundred hundred, nine hundred hundred hundred, ninetao hundred hundred, nine hundred hundred, ninetao hundred, nine hundred, ninetao, and seven."

This is codegolf, so the shortest code wins!

Answer 18

KoTH: Iterated Nash bargaining!

king-of-the-hill python

---

In this king of the hill challenge, you must play an iterated Nash bargaining game. You and your opponent must return a number between 1 and 100 which says how much money out of £100 you want.

If the total amount requested by the players is less than £100, both players get their request. If their total request is greater than that available, neither player gets their request. However, to spice things up, it is iterated — you will play 200 rounds against each opponent.

Your bot should be a Python 3.7 function that takes 4 inputs in the following order: your current points, your opponent's current points, all moves you have played (in a list) and all moves your opponent has played so far (also a list).

Here are two examples, one plays the opponents last move (and 50 on the first move):

def copycat(themp, myp, theml, myl):
    if len(theml) < 1:
        return 50
    else:
        return theml[-1]

The other plays 50 if they have less than 50 points, and 70 otherwise:

def fiftyseventybot(thempoints, mepoints, themlist, mylist):
    if thempoints <= 50:
        return 50
    else:
        return 70

Your bot will play 200 rounds against each opponent, in the 'round robin' fashion .Whoever ends up with the most points wins. Standard loopholes are banned.

Have fun!

---

Sandbox

This is my first question, make sure to tell me if anything could be worded better or if anything is spelled wrong etc.

Also tell me whether you think this is a good idea and if you have any ideas to add to it.

Is there not enough of an incentive to change if both players are going 50? if so, what incentives could be created?

There seems to be disagreement between @PeterTaylor and @Spitemaster. I would like to reach some kind of consensus on this. Could anyone possibly comment on what they think?

Answer 19

Check List for Duplicates

code-golf

Given a non-empty list of integers, return a truthy value if all entries are unique, and a falsey value of there are duplicate entries (or vice versa).

Examples

[1,2,3] -> false
[1,1,3] -> true
[1] -> false
[1,3,1,5] -> true

META: I couldn't find this as a challenge, but I cannot believe we didn't allready have this. Let me know if you can find anything related.

Answer 20

Super Permutations

Find the super permutation for a set of size n. A super permutation of a set is one string that contains all permutations of that set. Here is a helpful video by Matt Parker

Example

For a set of size 2 all the permutations are AB, BA but the super permutation is ABA because it contains the string AB and BA.
For a set of 3 all permutations are ABC,ACB,BAC,BCA,CBA,CAB and the super permutation is ABCABACBA.

Challenge

Given a certain size n (n>=1) find a super permutation of that set. To do this you have to use a pattern explained in the video.

Input

An integer greater than 0. This can be a function input superperm(n) or be taken from user input.

Output

super permutation of that sized set. This can either be printed out or the return value of a function

Sample Inputs

all of these are the shortest for that length but this is not a requirement.

    1: A
    2: ABA
    3: ABCABACBA
    4: ABCDABCADBCABDCABADABACDBACBDACBADCBA

Answer 21

Recently i made a post, but jumped the gun a little... I posted it before getting feedback and ended up getting it put on hold for being too arbitrary, but I have finally come here to get it properly fixed. Also I just got my Meta User fixed, so now I can post here!

Link to original post

Link to chat where all of this is being discussed

Basically I want to make the challenge where you create a quine that when given an input of 0 it outputs itself, and if given some other number it outputs a different quine. For example, abc outputting abc if given 0, abc outputting gef if given 1, abc outputting qwerty when given 255 etc... The scoring will be based on how little bytes can be used and how many extra different quines that it can output.

The problem comes with defining what defines different quine and how to balance the scoring so that coders will be encouraged to write short code, but still try to create different quines that aren't just altered copies of the original or each other

Examples of what not to do

abc      //original
abcd     //output
abcabcabc//output
aabc     //output
aaabc    //output
aaabbbccc//output

stuff like this wouldn't be allowed, I just don't know how to turn that into a rule that can't be abused.

What I want examples

abc      //original
gefh     //output
qwetryiop//output
uiop     //output
kerdp    //output
tttuiiree//output

Basically all of the output quines are different from each other, nor are they similar

And of course no examining source code.

Answer 22

Break Hello World (Cops)/Fix Hello World (Robbers)

Cops

Your job is to write a broken hello world program. What do I mean by that? Well, you write a valid hello world program, and make changes to it.

Your probably thinking "easy peasy", right? Well, there's one other condition: it must be hard to fix.

Anyways, for the actual rules. First you write a valid hello world program. That means:

• The characters sent to stdout form the string "Hello World!" exactly. Then the program halts gracefully (if given enough time and resources).
• Nothing is read from stdin or sent to stderr.
• No interacting with the operating system (i.e. no modifying files, randomness (unless it is pseudorandom and the seed is the same each run), internet, other commands, etc...)
• No using built-in or imported hashes or cryptographic primitives. If the program implements cryptographic primitives, that's fine though.
• Should work no matter how or on what platform it is run, assuming default options. The language it is written in should be reasonably cross platform and not cost money as well.

Now, make any changes you want to it. However, your score will be based on the edit distance between the valid and broken program (the lesser the better). The exact scoring will be described below.

The broken program can be any string you like (so calling it a "program" is technically a misnomer). Your submission will consist of:

• The broken program
• The edit distance between the valid and broken program, or any greater distance. (The reason you might want a greater distance is if the exact distance would reveal too much information. However, your score will suffer, and the robbers will have more flexibility, so be careful exercising this option). This number will be called your "brokenness" number.
• The language and language version of the valid program. This language should not be one written for this challenge.
• The sequence of literals appearing in the valid program, in the order they appear. (This is to encourage cops to scramble the program structure, not just hard coded values.)
• What the score will be if it is not cracked and after you reveal the solution.
• The date and time at which the program will be safe (as described below). (This way your program will be safe as soon as this time is reached, even if you have not had an opportunity to reveal the solution yet.) You may edit this in immediately after posting the solution, if you prefer, so that you will now the submission time.

After that, the robbers will have 168 hours (one week) to crack your submission from the date posted. If your submission is not cracked by then, your entry is safe. However, you can not claim your score until after you reveal the solution. To do this, edit your answer to include the valid program and an explanation as to why it works (if it takes a while to run). Also include what edits where made (since calculating the edit distance can be hard) and the word "safe" in the title.

How can your program be cracked? A robber just needs to write a valid hello world program (not necessarily the same as you wrote) whose edit distance from your broken program is less than or equal to your submission's brokenness number. The only other stipulation is that it has the same language and language version. In particular, it is not required to use the same literals as your program (this is to discourage cops from making their submission harder to crack this way).

And now for score. If the length of the broken program is L, the brokeness number is b, and the number of characters that can be used in your programming language is k, your score is (k^b)*(L+b)!/(L!b!), which you are trying to minimize. If your wondering were the heck that formula came from, it is very roughly the number of strings whose edit distance from your broken program is less than or equal to your submission's brokenness number (the exact value is hard to compute) (NOTE TO SANDBOX READERS: If you know a more accurate metric that isn't too complicated, let me know.). The idea is that the smaller the search space the robbers have to search, the more impressive it is if it does not get cracked. Also, please post the score in scientific notation for easy comparison.

This is code-challenge, so the submission which claims the lowest score wins!

Example Answer:

Python 2.7, score 7.5×10^53 (Safe)
Broken Program: salida "Hola Mundo!"
Brokenness Number: 18
Literals: "Hello World"
Safe Date: Feburary 12th, 3:42 PM UTC.

Valid program: print "Hello World!"
Edits: Make 7 replacements to get to saida "Holao dorld!". Make 4 deletions to get to saida "Hola do!". Make 4 insertions to get to salida "Hola Mundo!".
Explanation: Uses python's builtin print command to send `"Hello World!" to standard output.

Robbers

Welp, the cops did it again. They broke some hello world programs. Its your job to fix them.

Your probably thinking "easy peasy, I'll just rewrite it from scratch", right? Well, there's one other condition: you have a limited number of edits.

Anyways, for the actual rules. Pick a submission from the cop's thread that has not already been cracked, and is not safe. A submission is safe if it is over 168 hours (one week) old. The submission will have a broken hello world program, a brokenness number, and a programming language and language version, as well as some other useful information (including what literals in the cop's valid hello world program). Your submission must contain a valid hello world program in that language and language version whose edit distance to the broken program is less than or equal to the brokenness number. See the cop thread for what constitutes a valid hello world program. Also note that you are not required to use the same literals the cop used. They are only meant to give you a hint.

Your robber submission should consist of:

• A link to the cop entry you are trying to break.
• Your valid hello world program.
• An explanation as to why it works (if it takes a while to run).
• The edits you made to create the program (since calculating edit distance can be hard).

and then place a comment in the cops submission with a link to your submission. You get a point for each submission cracked. Note that only the first robber to crack a given cop submission gets a point. If you post a submission cracking a cop's submission, but it turns out another robber posted one before you, edit your submission to say that it is non-competing (or you can delete it if you want to). It is also non-competing if you crack a submission that is already safe.

This is cops-and-robbers, so whichever robber gets the most points wins!

Answer 23

Is This Randomizer Seed Beatable?

code-golf decision-problem graph

---

Randomizers of Pokemon, Zelda, Metroid games (among other games) have gained a lot of popularity in the last few years within the speedrunning community. Basically these are programs that shuffle around items, Pokemon, and even cosmetic things in a ROM of the game. It gives speedrunners a new and exciting challenge for a game they have played perhaps hundreds of times since items affect progression and can lead them to play the game very differently.

Randomizers also have logic that prevents them from making unbeatable configurations. We'll be looking at a simple, but generalized, form of this logic in this challenge.

Challenge Explanation

You will be given a list of rules as input describing some game world and its item requirements and a list of item locations. Your task is to determine if the item locations represent a beatable seed within the rules.

World Rules

The rules are a list of required items for accessing a location. A required item may have an associated quantity. For example, a simplified sampling of Super Metroid:

[] => Morph
[Morph] => BlueBrinstarBottomMissiles
[Missiles, Morph] => Bombs
[HighJump] => BlueBrinstarETank
[Morph, Bombs] => CrateriaDescentETank
...
[Supers, HighJump, Morph, Bombs] => Kraid
[Kraid] => Varia
[Varia] => Speed
[Varia, Speed] => IceBeam
...
[Kraid, Phantoon, Draygon, Ridley, Morph, IceBeam, Charge, 3 Missiles, 3 Supers, 3 ETank, Varia, Gravity] => END

It's possible for a location to be reachable by different sets of requirements. Conceptually, this means that any one set of requirements. Here's an example from Zelda: Ocarina of Time (referencing some glitches):

[DekuTreeBeaten] => ForestExit
[Stick] => ForestExit
[Nut] => ForestExit
[KokiriSword, DekuShield] => ForestExit

Keep in mind that the right hand side of the rules list in my example is actually a location id, not an item id. The special location id END indicates the ability to beat the game with those items.

Item Locations

You will receive a mapping of location IDs and which item they contain. For example:

KokiriSwordChest: HeartPiece
MidoHouse1: Hookshot
MidoHouse2: 5Rupees
...
DampeDig: ForestTempleBossKey
DampeRace1: NayrusLove
DampeRace2: HeartPiece
...
GoldGauntletsChest: DoubleMagic
...

What does it mean to be beatable?

A player begins a game with no items. If it is possible for the player to, through the continued acquisition of available items, reach the END location, then the seed is beatable. It doesn't matter if all items are obtainable as long as the END location is reachable.

This maps to a variant of graph reachability problems which can be solved relatively easily with a breadth-first search. (Other approaches may work as well)

Simple example (beatable)

World Rules:

[] => SwordChest
[] => ShieldChest
[Sword, Shield] => FireballScroll
[Fireball] => IceBeamScroll
[Fireball, Sword] => LightningScroll
[Fireball, IceBeam, Lightning] => END

Item Locations:

SwordChest: Fireball
ShieldChest: Sword
FireballScroll: Shield
IceBeamScroll: Lightning
LightningScroll: IceBeam

This seed is beatable with this item order: Fireball, Sword, Lightning, IceBeam. It's impossible to get the Shield because it's locked behind the FireballScroll which requires the Shield. But that doesn't matter because the END only requires the three elemental spells.

Simple example (unbeatable)

World Rules:

[] => SwordChest
[] => ShieldChest
[Sword, Shield] => FireballScroll
[Fireball, Shield] => IceBeamScroll
[Fireball, Sword] => LightningScroll
[Fireball, IceBeam, Lightning] => END

Item Locations:

SwordChest: Fireball
ShieldChest: Shield
FireballScroll: Sword
IceBeamScroll: Lightning
LightningScroll: IceBeam

This seed is unbeatable because Lightning is required, but is locked behind the Ice Beam Scroll, which requires the sword, which in turn is locked behind the Fireball Scroll, which itself requires the sword to access.

More test cases

More test cases can be found here.

Other Notes and Rules

• You can accept the world rules and the item locations in any convenient format or representation, given these restrictions:
  • When multiples of one item are in a requirements list, you can represent it by repeating that item multiple times or by having a quantity and item id.
  • Both item and location ids must be taken in as alphanumeric strings. (i.e. no converting it to numbers or other more convenient values before passing it into your program/function)
  • The sentinel value for the "beating the game" location id must be END, all caps, three letters.
• Item and location ids are case sensitive and must match exactly between the two inputs to be considered the same item or location
• Each location can be reached only once, even if it is reachable from multiple sets of requirements
• You may assume that every location id on the locations list appears at least once on the rules list and that there is at least one END in the rules list
• You may assume that each location id on the locations list appears exactly once and contains exactly one item.
• There is no concept of one-way doors that block off access to previously accessible locations. The requirements list is unordered.
• Location ids and item ids are separate and distinct. For instance, Morph as a location is different from Morph as an item.
• Output a truthy value for a beatable seed and a falsy value for an unbeatable seed.

Happy golfing!

---

Sandbox: there's a lot here. Any suggestions for explaining things better? Should I add more test cases?

Answer 24

MisterGeeky's query-to-list challenges:

^{It is up to you whether you interpret these challenges as following a pattern.}

---

Challenge 1:- Given an array of random numbers and a target number, sample pairs in the array whose sum is closest to the target.

Minimize the error function. To explain this challenge, I need elucidate on the random list.

L = [8.76, 7.89, 6.98, 9.99]

That's just a handmade random list. Yours can be auto-generated of any length.

Say target = 42.

Find a tuple made from cartesian LxL whose sum of elements is closest to target.

These are obviously not the best words to pose the challenge with, they will be refined. How close is this to golf?

Challenge 1.5:- Extend the above problem with all known operations, and even increase the number of numbers that can be taken at a time to reach the target.

op = ['*', '**', '^', '/', '+', '-']

Assume usual meaning for each, ** is sometimes for exponentiation but you can use it for tetration, similar to knuth's up arrow notation. '^' is either XOR or exponentiation. You have the liberty to choose operators. I meant operators known to you in general. Just normal arithmetic should even do.

op = ['+', '-', '*', '/']

I also allow any binary function that doesn't trivially output the target value.

---

Challenge 2:- Find list of Adjacent Elements to a given element or element position in any 4-dimensional matrix. (ie, m rows* n columns * p sheets * 4th dim whatever)

Even I'm not sure how this is golf. But I typically like to think there's only one approach that's the correct answer. Feel free to argue with me on that :D The idea is that this knowledge gives you a starting point to find n-neighbours of a cell location.

So, you typically have 8 directions of search (4 pure and 4 combined). You start with listing the immediate neighbours

Challenge 2.5:- Find specified number of adjacent elements of a point in n-space. You are free to either sample at random, use rank of the point or use minimum euclidean distances.

Here, you find n-neighbors of a given item. Points for creativity.

---

Challenge 3:- build a simple recommender, takes a query and outputs a list (recommender as a suggestions lister is not easily defineable)

Challenge 3.5:- improve recommendation efficiency (too advanced for golf)

Third challenge is anything that combines knowledge from first and second challenge.

...

The above are to be refined as golfing challenges, shortest code is the best code.

Please comment your thoughts below. Thanks.

Answer 25

Reducing switches in a binary matrix

A row's switch count is the amount of times the array switches from 1 -> 0 or 0 -> 1 when reading the array sequentially. As a Python function this looks like:

def row_switch_count(row):
    switch_total = 0

    last_r = row[0]

    for rr in row[1:]:
        if last_r != rr:
            switch_total += 1

        last_r = rr

    return switch_total

A matrix's switch count is the maximum switch count of all it's rows:

def mat_switch_count(bin_mat):
    max_switch = 0

    for row in bin_mat:
        count = row_switch_count(row)

        if max_switch < count:
            max_switch = count

    return max_switch

Write a function to reduce a matrix's switch count for each row to be less than a desired toggle count by permuting the elements in the nth column. You should permute as few columns as possible.

Permissible permutations

The only permutation allowed is moving the column. You can move a column's index, but you cannot mutate the column itself. For example, you cannot change a column [1, 0, 0] -> [0, 0, 1]. However, you can move a column within a matrix:

([1, 0, 0], ->  ([0, 0, 1],
 [0, 0, 0])      [0, 0, 0])

Input

A binary array with rows > 1 and cols > 5. The sum of all rows in any given column less than 1.

A desired_toggle_count >= rows.

Examples

Note the solutions are not unique and not all solutions need to be provided. However, there is guaranteed to be a solution, since the trivial solution where you sort all the columns, is valid.

desired_toggle_count=3
([1,0,1,0,1,0,0],
 [0,0,0,1,0,1,1]) 
=> 
([1,0,1,1,0,0,0],
 [0,0,0,0,1,1,1])

-----

desired_toggle_count=4
([1,0,1,0,1,0,0],
 [0,0,0,1,0,1,1])
=>
([1,0,1,0,0,0,1],
 [0,0,0,1,1,1,0])

or

([1,0,1,1,0,0,0],
 [0,0,0,0,1,1,1]))

----

desired_toggle_count=4
([1,1,1,0,1,0,1,0,0],
 [0,0,0,1,0,1,0,0,1])
=>
([1,1,1,0,1,0,0,0,1],
 [0,0,0,1,0,0,1,1,0])

or

([1,1,1,0,1,1,0,0,0],
 [0,0,0,1,0,0,1,1,0])

----

desired_toggle_count=5
([1,1,1,0,1,0,1,0,0],
 [0,0,0,1,0,1,0,0,1])
=> 
([1,1,1,0,1,0,1,0,0],
 [0,0,0,1,0,1,0,0,1])

----

desired_toggle_count=4
([1,0,1,0,1,0,1],
 [0,1,0,1,0,0,0],
 [0,0,0,0,0,1,0])
=>
([1,0,1,0,0,1,1],
 [0,1,0,0,1,0,0],
 [0,0,0,1,0,0,0])

Sandbox comments

I think this question might have too many requirements to be interesting? Brevity is the soul of wit and this question is not very brief.

Answer 26

(bit)Wise Images

Given a truth table and two images, use the truth table as a bitwise operation to the two images.

For example with the truth table:

  1 0
1 0 0
0 1 0

(Note that the top is the first image and the left is the second)

and the two images (0, 2, 4) (a 1x1 image, with the numbers being RGB values) and (30, 20, 10):

You would apply the above truth table to the numbers 0 and 30, of which's binary representations are 00000 and 11110. Using the truth table as a bitwise operation would get us 00000, or in decimal form 0.

This means that the red value of the first pixel would be 0.

Continuing this with the other RGB values would get us 2 and 4 for green and blue respectively.

So the output for this would be a 1x1 image with the only pixel having an RGB value of 0, 2, 4.

NOTES:

You can use any default input or output method.

You can assume that the two input images are the same dimensions.

You can support any image format you want as long as the image format supports RGB values from #000000 (0, 0, 0) to #ffffff (255, 255, 255).

The truth table can be in any format you want

Answer 27

Perfectly stable code

You are a.... Let's say prepared, programmer. You are working on the code to end all code, and it must be perfectly stable. No crashes, memory corruptions, mispellings, or anything else must get in your way. Everything else was set, but to your horrer you discovered that you had not accounted for the possiblity that the sun could actually flip a bit in your code! Naturally, you must now account for this.

The objective: A hello world program that still works if a single char is changed.

Questions:

• Has this been asked?
• What kinds of limits should I impose to make it possible? Allow 10% of chars to be safe, limit the charset to just ASCII, ect.
• Is it possible?

Answer 28

code-golfgamestime

Centurion Counter

The drinking game Centurion is extremely simple - 1 shot of alcohol (usually beer or cider) once a minute for 100 minutes.

Whilst playing the other day a friend commented that we didn't need the tracking app, and that we could have just written the program ourselves. So now it is your turn.

Task

Write a program that once every 60 seconds produces a beep or sound to alert players a minute has passed, and then add one to the counter of how many shots have been had.

The counter starts at 1 (the first shot) and then ends at 100 when the last counter is taken.

Answer 29

There doesn't seem to be a "l337 5P34K" challenge, or I have not yet found one. How about it? Simple string manipulation so it should fall under "C0D3 60LF", right? I.E, Leet speak encoder (challenge one), and leet speak decoder (challenge two).

Answer 30

Plot an NACA Airfoil

popularity-contestgraphical-output

NACA airfoils are described using a series of digits that represent the miscellaneous properties of the airfoil profile.

The purpose of this challenge is to receive an airfoil number as input, and plot the profile of the airfoil.

Background information:

4-digit NACA airfoils are generally described by their string NACA ABCC, where A,B are single digit integers, and CC is a 2-digit integer.

• A is the maximum camber as a percentage of the chord length. Eg. A=2 means that the camber is 2% of the chord length.
• B is the location (divided by 10) of maximum camber as a percentage of the chord length. Eg. B=4 means that point of maximum camber is 40% down the length of the chord.
• CC is the profile thickness as a percentage of the chord width. Eg. CC=12 means that the width of the airfoil is 12% of the maximum chord length.

Using the example given above, NACA2412, a suitable profile plot would look something like this:

Note that in the image above, the Red line is the camber line and the purple is representative of the symmetrical airfoil NACA 0012.

Any airfoils with a representative number of NACA 00XX are symmetrical in nature because they possess zero camber.

Possible scoring criteria are code-golf and popularity-contest

Any feedback is welcome. I also plan on having more challenges for the 5-digit and 6-digit profiles. Eventually, I will add equations to this post too.

Another way this challenge could be run would be to have the programmer return a series of points around the profile. This could be judged both for accuracy and quantity of points returned. If this approach is used, this would probably be a code-golf challenge.