# Sandbox for Proposed Challenges

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

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
• 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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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

Get the Sandbox Viewer to view the sandbox more easily!

# How could these rep and scores have happened?

Challenge: Given a reputation score, a count of questions with accepted answers, and a list of net votes on questions, calculate a sequence of actions that could have produced them. To keep this simple, here's a few simplifications from how Stack Exchange actually works:

• The only things that change reputation are upvotes on questions (+10), downvotes on questions (-2), and accepting an answer to a question (+2).
• The daily cap of 200 never comes into play.
• Votes are never retracted and accepts are never rescinded.

The minimum possible reputation of 1 still applies. If there are multiple sequences of actions that can produce the given state, then your program/function should return the shortest possible sequence (or one of the shortest, if there's multiple that are tied for the shortest). If there are no sequences of actions that can produce the given state, consider that Undefined Behavior, so it doesn't matter what your program does.

Examples/test cases:

• A user has 1 reputation, hasn't accepted any answers, and has no questions. The shortest possible sequence is "".
• A user has 33 reputation, has accepted 1 answer, and has questions with scores 2 and 1. A shortest possible sequence is "upvote, upvote, upvote, accept".
• A user has 3 reputation, hasn't accepted any answers, and has a question with score -5. The shortest possible sequence is "downvote, downvote, upvote, downvote, downvote, downvote, downvote".

The standard restrictions against loopholes apply. I/O may be in any convenient format. Examples: For input, [101,0,4,3,2,1] or (101,0,[4,3,2,1]) could mean a user with 101 reputation, 0 questions with accepted answers, and questions with scores 4, 3, 2, and 1. For output, the string UDA could mean "upvote, downvote, accept".

This is code golf, so the shortest program/function wins.

# Draw a Bracket

A bracket is a way of organizing a tournament as a tree structure. It follows several rounds of matches with half of the competitors being eliminated each round, until one competitor remains.

In this challenge you will be given as input a list of one digit $$\(0-9)\$$ integers as input representing competitors and you should output an ASCII representation of a bracket. The exact specifications are in the Output section of this challenge.

For example if the input is 1 2 3 4 5 6 7 8 then the output would be:

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


In this challenge the lower number is always the winner in a matchup.

## Input

The input will always be of length $$\2^n\$$ for some positive integer $$\n\$$, and will consist entirely of one digit numbers. You may take the integers as their representative characters instead if this pleases you.

## Output

I will explain precisely how the output is created momentarily, it is a bit hard.

## Scoring

This is the shortest answer in bytes wins.

• I fail to see how this is a bracket. – infinitezero Apr 13 '20 at 6:39
• I am worried because this says "you have a string of digits of uncertain length, and I'll explain the rest of the challenge later, it's a bit hard" and that's it. – the default. Apr 13 '20 at 15:47
• @mypronounismonicareinstate The length is explicitly $2^n$. I do have an example which should help get the idea across. Even though it is a simple idea it is just hard to put the idea in a very concrete specification in a ways that is not incredibly roundabout or esoteric. – Wheat Wizard Apr 13 '20 at 15:55
• @infinitezero I added an explanation of what a bracket is if that helps, I don't know if that resolves your issue. It is hard for me to know since this is very clearly a bracket to me. – Wheat Wizard Apr 13 '20 at 16:04
• The word "bracket" is ambiguous, but I could easily understand from the word "tournament" that the figure is the result of a tournament with $2^n$ players where the winner is deterministic. I guess you could draw the same figure rotated 90 degrees to help understanding the task. (And I once misunderstood it as "winner is always the left one" before I saw the line under the figure. It'd be better to randomize the example input a bit to make it clearer.) – Bubbler Apr 14 '20 at 0:08

The assignment logic may be used in a planning KoTH, in which a student bot chooses a full permutation from the classes and is awarded points from what preference they get.

# Assign classes fairly and satisfyingly code-golfarray-manipulation

### Background

In a school, students are signing up for after-school classes. However, the capacity of each class is limited. In order to facilitate class assignment, each student is required to fill in a questionnaire to show his/her preference to the classes by listing all classes in decreasing order of his/her interests.

You are assigned to help assigning classes to them. You want to maximally satisfy their preferences while being fair with the assignment. A student can be assigned with multiple classes.

### Challenge

Write a program or function that receives the following input:

• a list of classes with the corresponding capacities; and
• a list of students with their corresponding preference lists,

and output or return either:

• a list of class with the list of students being assigned to that class; or
• a list of students with their assigned classes.

You may use any reasonable alternative format for both input and output, for example, apart from receiving two arrays, you may choose to receive two strings, and especially for the second input (which requires a 2-D array), you may even have an input like this (first level delimiter \n, second level delimiter space):

1 2 3 4
4 2 3 1
1 3 2 4
2 3 4 1
3 4 1 2
4 1 2 3


To simplify the challenge, you may assume both classes and students are 0-indexed or 1-indexed. For the use of illustrating the requirements and samples, 1-indexing is used. You may also assume that each preference list is a full permutation of all classes.

The assignment requirements are as follows:

• Fairness: All students must have roughly the same amount of classes assigned to them, that is, for every $$\1\le i\le\text{[Number of students]}\$$, $$\left|{\text{[Number of classes assigned]}_i-\frac{\sum\text{[Class capacities]}}{\text{[Number of students]}}}\right|<1.$$
• Satisfaction: You should fulfill the preferences as well as possible. Specifically, you should fulfill as much first preferences as possible, then as much second preferences as possible, and so on. In case of having the same preference order, the classes should be assigned on first-come-first-served basis.

The fairness rule should be taken first if it conflicts with the satisfaction rule. Test case 3 is an example of handling such conflicts.

The program should terminate in finite time for all practical sizes of inputs.

### Test cases

Test case 1

Input:

classes = [2, 2, 2, 2],
students = [
[1, 2, 4, 3],
[2, 4, 1, 3],
[3, 4, 2, 1],
[4, 3, 2, 1]
]


Output:

classes = [
[1, 3],
[2, 1],
[3, 4],
[4, 2]
],
students = [
[1, 2],
[2, 4],
[3, 1],
[4, 3]
]


Explanation:

1. It is clear that all 1st priorities can be fulfilled because all of them are different. So each student gets his 1st priority.
2. Student 1 wants Class 2 as his 2nd priority, and Class 2 still has place for him. So he gets Class 2.
3. Student 2 wants Class 4 as his 2nd priority, and Class 4 still has place for him. So he gets Class 4.
4. Student 3 wants Class 4 as his 2nd priority, but Class 4 is already full. No place for him.
5. Student 4 wants Class 3 as his 2nd priority, and Class 3 still has place for him. So he gets Class 3.
6. Now each of the students except Student 3 has 2 classes already, so by the rule of fairness they are not considered in the subsequent assignments.
7. Only Class 1 has place for Student 3, so he gets his 4th priority.

Test case 2

Input:

classes = [2, 2, 2],
students = [
[3, 1, 2],
[2, 3, 1],
[2, 3, 1],
[3, 2, 1]
]


Output:

classes = [
[1, 2],
[2, 3],
[1, 4]
],
students = [
[3, 1],
[2, 1],
[2],
[3]
]


Explanation:

1. It is clear that all 1st priorities can be fulfilled because none of the classes was chosen by 3 or more students as their 1st priorities.
2. Student 1 wants Class 1 as his 2nd priority, and Class 1 still has place for him. So he gets Class 1.
3. Student 2 wants Class 3 as his 2nd priority, but Class 3 is already full. No place for him.
4. Student 3 wants Class 3 as his 2nd priority, but Class 3 is already full. No place for him.
5. Student 4 wants Class 2 as his 2nd priority, but Class 2 is already full. No place for him.
6. Now Student 1 has 2 classes already, so by the rule of fairness he is not considered in the subsequent assignments.
7. Student 2 wants Class 1 as his 3rd priority, and Class 1 still has place for him. So he gets Class 1.
8. All classes are already full, so no more seats can be assigned. Students 3 and 4 will only get 1 class each.

Test case 3

Input:

classes = [1, 1, 1, 2],
students = [
[1, 2, 4, 3],
[3, 4, 2, 1],
[2, 4, 3, 1],
[2, 4, 1, 3]
]


Output:

classes = [
[1],
[3],
[2],
[4, 2]
],
students = [
[1],
[3, 4],
[2],
[4]
]


Explanation:

1. It is clear that all 1st priorities except for Student 4 can be fulfilled.
2. If we ignore Student 4 and proceed to the second round, Student 2 and 3 will occupy the remaining seats and Student 4 will not get a place (which is disallowed by the fairness rule), so the 2nd priority of Student 4 will be considered first. Since Class 4 still has place for him, he gets Class 4.
3. Student 1 wants Class 2 as his 2nd priority, but Class 2 is already full. No place for him.
4. Student 2 wants Class 4 as his 2rd priority, and Class 4 still has place for him. So he gets Class 4.
5. All classes are already full, so no more seats can be assigned. All students get 1 class each, except Student 2, who gets 2 classes.

Test case 4

Input:

classes = [1, 1, 1, 2],
students = [
[1, 2, 4, 3],
[3, 4, 2, 1],
[2, 4, 3, 1],
[2, 1, 3, 4]
]


Output:

classes = [
[1],
[4],
[2],
[2, 3]
],
students = [
[1],
[3, 4],
[4],
[2]
]


Explanation:

1. It is clear that all 1st priorities except for Student 4 can be fulfilled.
2. If we ignore Student 4 and proceed to the second round, Student 2 and 3 will occupy the remaining seats and Student 4 will not get a place (which is disallowed by the fairness rule), so the 2nd priority of Student 4 will be considered first. However both Classes 1 and 3 are full, he can only get Class 4.
3. The remaining place for Class 4 goes to Student 2, and we have 3 1st priorities, 1 2nd priority and 1 4th priority fulfilled.
4. But this is not the best. By breaking the first-come-first-served rule for 1st priority, we can get the best - 3 1st priorities and 2 2nd priorities fulfilled.

### Winning Condition

This is a code-golf challenge, so the shortest submission for each language wins. Standard loopholes are forbidden.

# Euler's Geometry Puzzle

posted

• This probably needs a description of an incircle and circumcircle. As for what you ask, personally I believe the best thing to do with challenges like this is to say "you must meet <arbitrary precision> for the test cases, work in general, but you need not handle floating point errors" or something similar. – FryAmTheEggman Apr 12 '20 at 5:00
• Thanks for the suggestion. @FryAmTheEggman I'm not sure if I can give a good definition, so I linked the pages in wolfram mathworld. – newbie Apr 12 '20 at 5:36
• Since it is for triangles, the definitions can be fairly simple (even if finding them is still cryptic). In the interest of allowing people to understand what the challenge asks without requiring them to go to other websites, I think you can include a brief summary of the two definitions: incircle - the largest circle that fits inside the triangle, circumcircle - the circle that passes through each of the traingle's vertices. – FryAmTheEggman Apr 12 '20 at 15:37
• Done. Thanks! @FryAmTheEggman – newbie Apr 12 '20 at 15:46
• I don't think this is a very interesting challenge, as there is very likely no other beautiful formula for such a thing as the distance between the incenter and the circumcenter, so this is 2.5 challenges in one: "find the incircle radius", "find the circumcircle radius" and "substitute both into this formula". – the default. Apr 13 '20 at 15:44
• Hmm, but if you need to compute both the incircle radius and circumcircle radius, the formula can be simplified. (so the bytecount should be fewer than the sum of these two individual challenges, at least to me it's true) the last 0.5 is... for the context. @mypronounismonicareinstate – newbie Apr 13 '20 at 15:46
• I think something that might help with the challenge feeling like a few stapled together would be dropping the requirement that the two radii be included in the output. That way, golfing benefits from coupling are less hampered by needing to remember/store/output intermediate values. It is definitely possible that this won't fix the problem totally, but I think it should help. – FryAmTheEggman Apr 13 '20 at 16:01
• Sounds like a good idea to me. I'll look into it tomorrow. (I'm a bit afraid if there're some much easier way to calculate that value alone) – newbie Apr 13 '20 at 16:12
• @newbie For what it's worth, here's what a mildly golfed formula for d alone looks like: Try it online! – xnor Apr 13 '20 at 21:55
• Thanks! I did some more golf and it's 66 bytes now. Would it be a better idea to output say $R+r+d$? – newbie Apr 14 '20 at 1:29
• Alright, I would go with output $d$. – newbie Apr 14 '20 at 4:08

## Convert CSV to GeoJSON

Given an input in this CSV format:

Latitude,Longitude,Name,Value
-37,145,Melbourne,4500000
-34,150,Sydney,5000000


produce this output (GeoJSON):

{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {
"Name": "Melbourne",
"Value: "4500000"
},
"geometry": {
"type": "Point",
"coordinates": [-37, 145]
}
}
],
...
}


You may assume that:

• The input will always be a well formed CSV file in this format. (No meta rows/front matter, no quoted strings, no spaces between fields, no problematic characters.)
• The input will contain one "Longitude" and one "Latitude" column, capitalised that way.
• The Latitude and Longitude columns may not be in that order, nor necessarily the first two columns.
• The number of other columns may be zero or many. They must all be converted.
• There will always be one header row. There may not be any data rows.

Notes regarding the output:

• must be valid GeoJSON (test with geojsonlint.com if you're not sure). Note: There must be a properties object, even if it is {}.
• is correct if it is semantically equivalent. (The order of keys does not matter).
• Whitespace does not matter.
• Treat all properties as strings.

Input and output in any of the standard ways for text input/output. Note the output must be text, not an object. (Ie, in JavaScript, use JSON.stringify())

• What's the scoring mechanism? Code Golf I assume? – math junkie Apr 24 '20 at 18:34

# Finitly inverese in base N code-golfmath

Your task is when given a base N (you can assume it's $$\ \geq2 \$$) you need to output all natural numbers for which the decimal expansion of $$\ \frac{1}{x} \$$ in base N is finite.

## Input

You can take the base N in any reasonable format, and you also may take an additional number N, depending on what output format you chose.

## Output

You have 3 options for the output format:

• Take a number n and output the n-th number in the sequence
• Take a number n and output first n numbers in the sequence
• Take no additional input and output the list indefinitely

# Test Cases

10 -> [1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, 128, 160, 200, 250, 256, 320, 400, 500, 512, 625, 640, 800, 1000, 1024, 1250, 1280, 1600, 2000, 2048, 2500, 2560, 3125, 3200, 4000, 4096, 5000, 5120, 6250, 6400, 8000, 8192, 10000, ...]
2 -> [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...]

• So basically numbers such that their set of prime factors is a subset of N's set of prime factors? (assuming no repetitions in sets) – the default. Apr 16 '20 at 10:31
• I'm not sure, but from what I've seen it seems like it – Command Master Apr 16 '20 at 12:33

## This Question Has _____ Views code-golfstack-exchange-api

posted

• I think currently the challenge will only be who can get the shortest domain that'll respond with the output. I think you should limit the challenge to only accessing the stack exchange api, and not any other website – Command Master Apr 16 '20 at 7:59
• @CommandMaster But any other domain will be wrong as soon as the number of views goes up. The program should always print out the number of views this question has at the moment you actually run the program. – izlin Apr 16 '20 at 8:48
• someone can register a domain which will retrive the live number – Command Master Apr 16 '20 at 8:51
• @CommandMaster that is either the "Fetching the desired output from an external source" or the "Outsourcing the real answer" loophole. – the default. Apr 16 '20 at 10:30

# Making a programable computing chip

Make a programable chip with 8000 commands ROM and 48 16-bit unsigned words RAM initalized with zero.

These commands should be supported:

a = b + c  # mod 65536
a = b - c
a = b * c
a = b / c  # undefined behavior if c==0
a = b % c
a = b > c  # return 0 or 1
a = b >= c
a = b == c
a = b != c
if a goto b
if !a goto b
call a, b  # store ip of next command to b and goto a, then can return
input a
output a
a = [b] # You can decide constant k and l, such that [kn+l] is rn.
[a] = b # Using undefined [n] is UB


where a, b, c can be r0-r47 or a constant of a 16-bit integer or the ip of a command. Writing to a constant is a nop, so input 42 discards an input. Mixing ip and integer, running out of commands are undefined behavior.

For example,

L1: input r1
r0 = r0 + r1
output r0
if !0 goto L1
r2 = r1 + L1


takes input, and output sum of all inputs modulo 65536. r2 = r1 + L1 is undefined behavior, but since it's never executed it's not a problem.

The circuit consists of controlled gates (x,y,c,t), meaning that wire x and wire y are connected if wire c was active(t=1) or inactive(t=0), and programable wire (x,y,0,0), meaning that wire x and wire y can be programmed to be connected.

At the beginning, none of the wires, except IO wires(discuss later), is active. In each step, any wire connected to wire 0, whether directly or indirectly, is active.

IO is used to connect multiple such component. It contains 18 wires, where 16 of them store an integer to be passed, and two A and B meaning if there's data on the wire. When sender send, sender negate A; when reciever recieve, B negated. Therefore, there's data on the wire iff A!=B.

We write A on input, B on input, A on output, and B on output of the chip, as 4, 8, 5, 9, respectively, and the 16-bit input on 16-31, output on 32-47. You can active wires where you are expected to read from, but your chip should handle with another such chip (so if you write to input, you should handle cases when output is inputted).

For example, {(0,5,4,1),(0,8,9,1)} output zero whenever recieving an input.

You should submit a circuit (a set of 4-elem tuples) and a compiler. Smallest circuit win.

Given a $$\ 20 \times 20 \$$ grid, start at any arbitrary point. Then starting from this point, draw a sequence of straight lines each attached to two points on the grid. In addition, the lines must be in strictly increasing length, and such that no two intersect or touch each other. Call the number of lines drawn $$\ n \$$. The diagram below shows an example of a smaller $$\ 5 \times 5 \$$ grid, where $$\ n = 5 \$$. However, the maximum length for a $$\ 5 \times 5 \$$ grid is actually $$\ n = 9 \$$ (Try to find it yourself!).

This is , meaning the answer with the largest $$\ n \$$ wins!

Checker program coming soon

## Sandbox

• Anything unclear?
• How to position image on the right and text on the left (it looks better)
• Related: A226595, which lists exact values up to grid size 15. The C++ program's comment says it took 1001 minutes (~17 hours) to get the exact answer for 15. – Bubbler Apr 22 '20 at 2:05

# Fixed Point of cos(x)

Fixed points are any such values where, given a function f, x = f(x) = f(f(x)) = . . .

There exists a "fixed point" for the cosine function, where x = cos(x) = cos(cos(x))= . . .  (you may have unknowingly come across this by repeatedly pressing "cos" on a scientific calculator).

Using the knowledge that x = f(x), one can think of a fixed point as the intersection of the graphs of y = x and y = f(x). If we let f(x)=cos(x), the graph looks like this:

Your task is to calculate the x-value of the fixed point of cos(x) 0.73908513 . . .  to at least 3 digits' precision (i.e. at least as far as 0.739).

## Rules

• No input is to be taken for the program

• This is so the shortest answer (in bytes) wins

# Questions for Sandbox:

• Is the question clear enough as it is written?

• I have searched, but I am still paranoid: is this a duplicate?

• Are the tags and suitable? Or should I also include ?

• Should I allow input? It seems unnecessary for solving the problem to me

• How far should the precision be extended?

• Very nice question! I think the code-golf tag is suitable for all code-golf challenge. P. S. If I'm getting it right one can repeatedly take cosine to solve this right? – null Apr 23 '20 at 0:49
• I think this would be a more interesting challenge if the question were: "Given a function f(x), find a fixed point of f". In its current state, this challenge simplifies to: "print the number 0.739" – math junkie Apr 23 '20 at 0:49
• @HighlyRadioactive That is correct – golf69 Apr 23 '20 at 0:50
• Who cast the downvote? – null Apr 23 '20 at 0:50
• @mathjunkie I think that was already done here, and besides, ideally they would actually calculate the value instead of simply printing it – golf69 Apr 23 '20 at 0:52
• I thought I remembered this being a duplicate, but I see you've searched already, and I didn't find anything on a quick look. I'd suggest having the output be something like 100 digits of precision to discourage hardcoding, or give the required precision as an input, though these do mean floating-point won't work. – xnor Apr 23 '20 at 2:27
• Wait, I found the duplicate: Approximate the Dottie number – xnor Apr 23 '20 at 2:32

# Boolean Variable Satisfiability code-golf

You are given a logical expression containing 'true', 'false', 'variable' and some common boolean operators. Assuming that all variables are independent and can be freely set to either true or false, is it possible assign values to the variables such that the expression evaluates to true?

For example, the expression true and variable and not variable can indeed evaluate to true (if the first variable is true and the second is false). However, the expression false and variable cannot ever evaluate to true, regardless of what values you set the variable to.

Note that you are not required to construct a solution; you only need to determine whether or not it exists.

# Input

You are given an expression in Reverse Polish notation, using the following symbols:

• T - True
• F - False
• V - Variable
• & - Logical AND
• | - Logical OR
• ^ - Logical XOR
• ! - Logical NOT

As an example, TFV!T^|& represents the expression true and (false or (not variable xor true)).

# Output

The program should output a truthy value iff the expression can be evaluated to true for some set of variable assignments. Otherwise, a falsy value should be outputted.

# Examples

Here are a few example expressions and their expected outputs:

TF&
False

FV|V&
True

VV!&
True

VV^!
True

VV&F|VVT|!&V!&&
False

VV&F|VVT|!&V!^&
True

TFV!T^|&
True

VT|!V&F|VF&!T^^
False


# Scoring

This is , so the shortest answer wins.

I've written this as if I would post it right away. However, seeing as this is the first challenge I've written for this site, any and all input is welcome so as to make sure it's of an acceptable standard.

• Thanks you for using the sandbox. – Adám Apr 23 '20 at 12:00
• One thing that bothers me here is the combination of two tasks: a) parsing the RPN b) finding if the expression is satisfiabiable. – Adám Apr 23 '20 at 12:13
• So every appearance of V is independent of each other? Then it can be solved in O(n) by resolving each inner node into T/F/V on the fly. Cool challenge. But as Adám said, the task right now is two tasks combined, and we want to get it focused to b). My suggestion is to allow the programs to take any unambiguous format that can describe a statement as input. That includes RPN, PN, fully parenthesized infix, and (most notably) a syntax tree. – Bubbler Apr 24 '20 at 0:08

# Constellation Enumeration in Game of Life

Yet another trivial Conway's Game of Life challenge.

A stable constellation is a still life that is composed of two or more non-interacting objects.

You task is to take the valid object list, and output a list of all possible constellations. The objects cannot be rotated or reflected. All of the objects are still lives themselves.

A sample implementation is here.

## Sandbox

• Any advices on the input and output format? Plain text, RLE, or every Golly-accepable form?
• Any test cases?
• Other recommendations.
• What would the scoring mechanism be? Code Golf? – math junkie Apr 23 '20 at 16:03
• @mathjunkie Damn, I forgot to specify! Code-golf, obviously. – null Apr 23 '20 at 16:04
• The recommended I/O format is "any sensible format that can describe GoL states". Also, the challenge needs much more detail. How exactly should we combine the input objects? Should we follow a strict order in generating them? Is there a limit in output grid size? How many outputs should we generate? First N? Infinity? We don't want to read such a long sample implementation, especially one that has an external dependency (do you see import golly as g at the top?). – Bubbler Apr 23 '20 at 23:47
• A challenge needs to be self-contained. You need to briefly include what GoL is, what the rules are, what a still life is, and whatever concept you need in order to describe the task and I/O format. You might as well need to (at least roughly) describe the algorithm in the sample implementation in English words. – Bubbler Apr 23 '20 at 23:52

# Convert NFA to DFA as quickly as possible.

Input

Your input will be an NFA. In order to be able to test your code, it needs to be able to handle an NFA in the following format. This is taken directly from GAP (and slightly simplified).

Automaton( Type, Size, Alphabet, TransitionTable, Initial, Accepting )


For the input, Type will always be "nondet". Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are lists of non-negative integers not greater than the size of the automaton are also allowed. Initial and Accepting are, respectively, the lists of initial and accepting states.

Example input:

Automaton("nondet", 4, 2, [[[], [2], [3], [1, 2, 3, 4], [2, 4]],
[[], [1, 3, 4], [1], [2, 4]]], [1], [2, 3])


This is slightly easier to read as a transition table.

   |  1    2             3                4
--------------------------------------------------
a |      [ 2 ]         [ 1, 2, 3, 4 ]   [ 2, 4 ]
b |      [ 1, 3, 4 ]   [ 1 ]            [ 2, 4 ]
Initial state:    [ 1 ]
Accepting states: [ 2, 3 ]


Output

Your output must be a DFA that is equivalent to the input NFA. There is no need for your DFA to be minimal. For the output, Type will always be "det". Size is a positive integer representing the number of states of the automaton. Alphabet is the number of letters of the alphabet. TransitionTable is the transition matrix. The entries are non-negative integers not greater than the size of the automaton. The states should be labelled by consecutive integers. Initial and Accepting are, respectively, the lists of initial and accepting states. In the case of the example above, this would be:

Automaton("det", 2, 2, [[2, 2], [2, 2]], [1], [])


As a transition table this is:

   |  1  2
-----------
a |  2  2
b |  2  2
Initial state:   [ 1 ]
Accepting state: [  ]


(It is now clear this is a DFA that will not accept any input strings.)

# Test cases:

1. Input:
Automaton("nondet",2,4,[[[1], [2]], [[2], []], [[2], []] , [[1], [2]]],[1],[1, 2]))


As a transition matrix:

   |  1       2
-------------------
a | [ 1 ]   [ 2 ]
b | [ 2 ]
c | [ 2 ]
d | [ 1 ]   [ 2 ]
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]


Here is the diagram of the NFA.

Output:

Automaton("det",3, 4,[[1, 2, 3], [2, 3, 3], [2, 3, 3], [1, 2, 3]], [1],[1, 2])


As a transition matrix:

   |  1  2  3
--------------
a |  1  2  3
b |  2  3  3
c |  2  3  3
d |  1  2  3
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]


Here is the diagram of the DFA.

1. Input:
Automaton("nondet",7,4,[[[1, 3, 4, 5], [2], [3], [3, 4], [3, 5], [], []], [[2, 3, 4, 7], [3], [], [], [3, 7], [3, 4], []], [[2, 3, 5, 6], [3], [], [3, 6], [], [], [3, 5]], [[1, 3, 6, 7], [2], [3], [], [], [3, 6], [3, 7]]],[1],[1, 2, 3, 4, 5, 6, 7])


Output:



1. Input:
Automaton("nondet",12, 4,[[[1, 3, 5, 6], [2, 4, 7, 8], [3], [6], [3, 5], [3, 6], [4, 7], [4, 8], [4, 7], [4, 8], [], []], [[2, 3, 5, 10], [3, 4, 7, 12], [6], [], [4, 7], [3, 10], [], [4, 12], [3, 5], [4, 12], [4, 7], []], [[2, 3, 6, 9], [3, 4, 8, 11], [6], [], [3, 9], [4, 8], [4, 11], [], [4, 11], [3, 6], [], [4, 8 ]], [[1, 3, 9, 10], [2, 4, 11, 12], [3], [6], [4, 11], [4, 12], [], [], [3, 9], [3, 10], [4, 11], [4, 12]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])


Output:

Automaton("det",39, 4,[[1, 2, 3, 3, 5, 24, 7, 8, 22, 20, 8, 32, 18, 18, 3, 19, 25, 18, 19, 20, 25, 22, 23, 24, 25, 25, 24, 23, 5, 2, 35, 32, 19, 19, 35, 36, 36, 36, 36], [1, 38, 1, 23, 15, 9, 11, 26, 23, 28, 26, 10, 9, 26, 1, 3, 22, 26, 3, 28, 22, 23, 1, 15, 3, 3, 15, 1, 28, 27, 10, 27, 23, 23, 38, 15, 28, 15, 28], [1, 5, 1, 1, 1, 4, 12, 6, 6, 31, 31, 37, 37, 30, 5, 5, 29, 37, 3, 21, 4, 21, 4, 4, 4, 29, 30, 29, 1, 5, 29, 37, 5, 3, 29, 3, 3, 2, 2], [1, 16, 3, 4, 3, 21, 7, 18, 33, 39, 14, 13, 13, 14, 15, 16, 17, 18, 19, 34, 21, 34, 3, 19, 19, 16, 38, 15, 4, 33, 17, 18, 33, 34, 16, 19, 34, 38, 39]],[7],[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39])

1. Input:
Automaton("nondet",25,4,[[[1, 3, 6, 7], [2, 4, 8, 9], [3, 5, 10, 11], [6], [7], [3, 5, 6, 10, 18], [3, 5, 7, 11, 19], [4, 8], [4, 9 ], [5, 10], [5, 11], [4, 5, 8, 10, 22], [4, 5, 9, 11, 23], [5, 10], [5, 11], [], [], [5, 10, 18], [5, 11, 19], [5, 10, 22], [5, 11, 23 ], [], [], [], []], [[2, 3, 6, 13], [3, 4, 8, 15], [4, 5, 10, 17], [7], [], [4, 5, 8, 10, 18], [3, 5, 13, 17, 21], [5, 10], [4, 15], [], [5, 17], [3, 5, 6, 10, 22], [4, 5, 15, 17, 25], [4, 8], [5, 17], [5, 10], [], [], [5, 17, 21], [], [5, 17, 25], [5, 10, 18], [], [5, 10, 22], []], [[2, 3, 7, 12], [3, 4, 9, 14], [4, 5, 11, 16], [7], [], [3, 5, 12, 16, 20], [4, 5, 9, 11, 19], [4, 14], [5, 11], [5, 16], [], [4, 5, 14, 16, 24], [3, 5, 7, 11, 23], [5, 16], [4, 9], [], [5, 11], [5, 16, 20], [], [5, 16, 24], [], [], [5, 11, 19], [], [5, 11, 23]], [[1, 3, 12, 13], [2, 4, 14, 15], [3, 5, 16, 17], [6], [7], [4, 5, 14, 16, 20], [4, 5, 15, 17, 21], [5, 16], [5, 17], [], [], [3, 5, 12, 16, 24], [3, 5, 13, 17, 25], [4, 14], [4, 15], [5, 16], [5, 17], [], [], [], [], [5, 16, 20], [5, 17, 21], [5, 16, 24], [5, 17, 25]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25])


Output:

Automaton("det",266,4,[[1, 127, 50, 50, 115, 249, 50, 8, 257, 10, 151, 12, 13, 14, 81, 78, 34, 106, 137, 107, 21, 22, 82, 89, 71, 43, 43, 62, 63, 63, 44, 10, 179, 171, 214, 265, 206, 38, 137, 152, 21, 151, 71, 22, 41, 41, 47, 13, 49, 50, 50, 210, 50, 210, 116, 90, 64, 49, 207, 207, 207, 62, 232, 64, 64, 89, 151, 236, 236, 70, 71, 236, 116, 260, 128, 75, 13, 38, 77, 133, 14, 82, 13, 13, 77, 235, 64, 64, 231, 206, 138, 91, 91, 206, 90, 264, 137, 169, 10, 10, 41, 71, 232, 228, 232, 21, 21, 107, 106, 110, 111, 266, 256, 114, 114, 116, 251, 251, 116, 114, 114, 111, 266, 260, 122, 182, 127, 128, 129, 213, 132, 132, 129, 49, 49, 138, 138, 138, 249, 71, 43, 43, 210, 235, 183, 214, 132, 265, 206, 138, 232, 64, 64, 153, 153, 64, 152, 152, 82, 236, 236, 82, 116, 116, 64, 207, 266, 64, 231, 169, 171, 250, 227, 70, 175, 175, 176, 10, 47, 178, 178, 110, 111, 266, 260, 122, 266, 127, 213, 49, 49, 152, 257, 153, 257, 90, 90, 183, 250, 264, 62, 228, 229, 82, 82, 206, 64, 266, 249, 249, 249, 242, 213, 214, 64, 116, 114, 114, 50, 50, 236, 236, 261, 115, 152, 251, 8, 228, 229, 229, 231, 232, 237, 235, 235, 236, 237, 235, 235, 235, 235, 235, 235, 242, 242, 242, 115, 251, 249, 250, 116, 116, 116, 207, 64, 265, 266, 257, 256, 266, 264, 261, 260, 264, 265, 266], [1, 125, 1, 114, 114, 121, 115, 3, 23, 19, 13, 15, 230, 28, 201, 202, 16, 84, 123, 103, 105, 208, 114, 84, 172, 199, 199, 119, 83, 83, 123, 170, 16, 31, 27, 26, 25, 104, 102, 23, 28, 13, 120, 208, 48, 103, 19, 230, 239, 1, 114, 218, 115, 219, 82, 140, 23, 208, 204, 216, 216, 119, 174, 119, 119, 84, 13, 115, 115, 50, 120, 50, 82, 204, 262, 79, 230, 104, 203, 85, 28, 114, 230, 230, 203, 3, 23, 119, 96, 96, 96, 123, 102, 140, 208, 3, 200, 200, 98, 97, 103, 120, 119, 120, 119, 28, 105, 103, 105, 54, 3, 23, 141, 1, 250, 50, 82, 114, 50, 1, 250, 3, 3, 219, 219, 125, 54, 263, 124, 124, 27, 124, 223, 208, 239, 25, 208, 208, 120, 120, 217, 217, 217, 120, 120, 142, 142, 141, 140, 140, 174, 174, 174, 204, 216, 23, 119, 23, 250, 114, 114, 250, 162, 162, 159, 205, 159, 159, 208, 123, 170, 1, 219, 50, 208, 208, 123, 177, 177, 19, 170, 173, 172, 172, 199, 199, 23, 186, 185, 184, 184, 23, 120, 216, 23, 140, 208, 120, 1, 3, 119, 120, 114, 114, 250, 239, 119, 3, 121, 3, 120, 219, 212, 212, 23, 50, 1, 250, 1, 114, 50, 114, 219, 114, 23, 114, 3, 120, 114, 114, 208, 119, 125, 121, 3, 50, 54, 120, 3, 120, 121, 3, 120, 218, 219, 217, 114, 114, 3, 1, 250, 250, 250, 253, 252, 173, 172, 120, 125, 3, 3, 219, 219, 3, 54, 3], [1, 1, 249, 249, 6, 1, 1, 247, 7, 130, 167, 17, 11, 66, 33, 33, 131, 136, 10, 32, 150, 9, 112, 36, 149, 112, 149, 56, 167, 37, 181, 130, 35, 147, 139, 51, 139, 11, 10, 234, 147, 37, 148, 113, 136, 136, 146, 24, 249, 1, 1, 249, 249, 249, 139, 6, 238, 127, 134, 238, 134, 9, 148, 238, 134, 167, 36, 50, 249, 247, 73, 249, 51, 139, 112, 167, 76, 76, 11, 167, 80, 73, 67, 66, 66, 135, 58, 58, 112, 139, 233, 100, 100, 2, 6, 95, 10, 32, 130, 130, 99, 94, 94, 56, 149, 150, 147, 150, 136, 51, 51, 51, 7, 51, 51, 51, 7, 6, 139, 139, 139, 2, 58, 134, 139, 7, 1, 112, 112, 249, 238, 238, 112, 249, 127, 238, 233, 238, 1, 149, 112, 149, 249, 135, 7, 139, 238, 51, 139, 238, 112, 238, 233, 234, 234, 134, 234, 190, 112, 50, 249, 73, 139, 51, 238, 134, 51, 134, 148, 32, 147, 145, 145, 145, 258, 259, 180, 130, 146, 189, 189, 51, 51, 134, 134, 139, 2, 1, 249, 127, 249, 191, 191, 191, 188, 188, 188, 188, 198, 197, 196, 196, 195, 187, 187, 139, 233, 134, 127, 127, 127, 49, 249, 139, 243, 211, 211, 211, 210, 210, 210, 210, 95, 209, 241, 209, 126, 117, 117, 9, 112, 112, 50, 50, 50, 50, 50, 50, 49, 49, 127, 127, 127, 249, 249, 249, 7, 7, 1, 247, 51, 139, 211, 134, 134, 51, 51, 7, 7, 2, 126, 145, 139, 247, 51, 51], [1, 51, 3, 4, 4, 7, 7, 50, 73, 61, 11, 12, 40, 109, 101, 93, 45, 18, 19, 20, 21, 64, 161, 29, 193, 118, 193, 65, 11, 42, 19, 59, 30, 46, 163, 164, 163, 40, 39, 57, 46, 42, 246, 60, 18, 21, 61, 158, 72, 50, 51, 53, 53, 3, 55, 55, 57, 246, 156, 64, 65, 64, 155, 64, 65, 11, 29, 68, 69, 236, 160, 72, 73, 55, 157, 11, 154, 154, 40, 11, 46, 160, 225, 192, 192, 86, 87, 88, 157, 118, 155, 19, 39, 74, 161, 239, 92, 92, 166, 254, 20, 144, 88, 240, 65, 109, 108, 21, 21, 50, 50, 73, 73, 50, 247, 236, 73, 161, 72, 3, 5, 54, 86, 239, 3, 51, 50, 64, 64, 161, 165, 64, 157, 161, 245, 165, 60, 64, 51, 240, 161, 240, 4, 144, 51, 55, 57, 73, 55, 57, 157, 157, 155, 57, 64, 156, 64, 87, 118, 160, 161, 248, 163, 164, 165, 168, 164, 168, 60, 19, 108, 3, 3, 72, 64, 60, 19, 194, 194, 61, 59, 247, 247, 193, 193, 5, 74, 7, 69, 244, 69, 156, 240, 65, 74, 74, 246, 143, 219, 86, 88, 144, 222, 222, 226, 72, 60, 239, 52, 54, 143, 239, 72, 72, 215, 221, 219, 224, 219, 220, 221, 222, 239, 220, 215, 222, 54, 160, 160, 161, 64, 64, 160, 68, 236, 236, 236, 160, 239, 240, 244, 245, 246, 69, 72, 161, 51, 160, 50, 50, 248, 118, 226, 255, 255, 248, 248, 160, 160, 245, 245, 72, 72, 236, 236, 236]],[12],[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266])

1. Input:
Automaton("nondet",38,4,[[[1, 3, 7, 8], [2, 4, 9, 10], [3, 5, 11, 12], [4, 6, 13, 14], [7], [8], [3, 5, 7, 11, 23], [3, 5, 8, 12, 24], [4, 6, 9, 13, 25], [4, 6, 10, 14, 26], [5, 11], [5, 12], [6, 13], [6, 14], [4, 5, 9, 11, 31], [4, 5, 10, 12, 32], [5, 6, 11, 13, 33], [5, 6, 12, 14, 34], [6, 13], [6, 14], [], [], [5, 11, 23], [5, 12, 24], [6, 13, 25], [6, 14, 26], [5, 11, 31], [5, 12, 32], [6, 13, 33], [6, 14, 34], [6, 13, 25], [6, 14, 26], [], [], [6, 13, 33], [6, 14, 34], [], []], [[2, 3, 7, 16], [3, 4, 9, 18], [4, 5, 11, 20], [5, 6, 13, 22], [8], [], [4, 5, 9, 11, 23], [3, 5, 16, 20, 28], [5, 6, 11, 13, 25], [4, 6, 18, 22, 30], [6, 13], [5, 20], [], [6, 22], [3, 5, 7, 11, 31], [4, 5, 18, 20, 36], [4, 6, 9, 13, 33], [5, 6, 20, 22, 38], [5, 11], [6, 22], [6, 13], [], [6, 13, 25], [5, 20, 28], [], [6, 22, 30], [6, 13, 33], [5, 20, 36], [], [6, 22, 38], [5, 11, 23], [6, 22, 30], [6, 13, 25], [], [5, 11, 31], [6, 22, 38], [6, 13, 33], []], [[2, 3, 8, 15], [3, 4, 10, 17], [4, 5, 12, 19], [5, 6, 14, 21], [8], [], [3, 5, 15, 19, 27], [4, 5, 10, 12, 24], [4, 6, 17, 21, 29], [5, 6, 12, 14, 26], [5, 19], [6, 14], [6, 21], [], [4, 5, 17, 19, 35], [3, 5, 8, 12, 32], [5, 6, 19, 21, 37], [4, 6, 10, 14, 34], [6, 21], [5, 12], [], [6, 14], [5, 19, 27], [6, 14, 26], [6, 21, 29], [], [5, 19, 35], [6, 14, 34], [6, 21, 37], [], [6, 21, 29], [5, 12, 24], [], [6, 14, 26 ], [6, 21, 37], [5, 12, 32], [], [6, 14, 34]], [[1, 3, 15, 16], [2, 4, 17, 18], [3, 5, 19, 20], [4, 6, 21, 22], [7], [8], [ 4, 5, 17, 19, 27], [4, 5, 18, 20, 28], [5, 6, 19, 21, 29], [5, 6, 20, 22, 30], [6, 21], [6, 22], [], [], [3, 5, 15, 19, 35], [3, 5, 16, 20, 36], [4, 6, 17, 21, 37], [4, 6, 18, 22, 38], [5, 19], [5, 20], [6, 21], [6, 22], [6, 21, 29], [6, 22, 30], [], [], [6, 21, 37], [6, 22, 38], [], [], [5, 19, 27], [5, 20, 28], [6, 21, 29], [6, 22, 30], [5, 19, 35], [5, 20, 36], [6, 21, 37], [6, 22, 38]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38])


Output

1. Input:
Automaton("nondet",67,4,[[[1, 3, 8, 9], [2, 4, 10, 11], [3, 5, 12, 13], [4, 6, 14, 15], [5, 7, 16, 17], [8], [8], [3, 5, 8, 12, 28], [3, 5, 9, 13, 29], [4, 6, 10, 14, 30], [4, 6, 11, 15, 31], [5, 7, 12, 16, 32], [5, 7, 13, 17, 33], [6, 14], [6, 15], [ 7, 16], [7, 17], [4, 5, 10, 12, 40], [4, 5, 11, 13, 41], [5, 6, 12, 14, 42], [5, 6, 13, 15, 43], [6, 7, 14, 16, 44], [6, 7, 15, 17, 45], [7, 16], [7, 17], [], [], [5, 7, 12, 16, 28, 32, 52], [5, 7, 13, 17, 29, 33, 53], [6, 14, 30], [6, 15, 31], [7, 16, 32], [7, 17, 33], [5, 7, 12, 16, 40, 44, 56], [5, 7, 13, 17, 41, 45, 57], [6, 14, 42], [6, 15, 43], [7, 16, 44], [7, 17, 45], [6, 7, 14, 16, 30, 32, 60], [6, 7, 15, 17, 31, 33, 61], [7, 16, 32], [7, 17, 33], [], [], [6, 7, 14, 16, 42, 44, 64], [6, 7, 15, 17, 43, 45, 65], [7, 16, 44], [7, 17, 45], [], [], [7, 16, 32, 52], [7, 17, 33, 53], [7, 16, 44, 56], [7, 17, 45, 57], [7, 16, 32, 60], [7, 17, 33, 61], [7, 16, 44, 64], [7, 17, 45, 65], [], [], [], [], [], [], [], []], [[2, 3, 8, 19], [3, 4, 10, 21], [4, 5, 12, 23], [5, 6, 14, 25], [6, 7, 16, 27], [8], [], [4, 5, 10, 12, 28], [3, 5, 19, 23, 35], [5, 6, 12, 14, 30], [4, 6, 21, 25, 37], [6, 7, 14, 16, 32], [5, 7, 23, 27, 39], [7, 16], [6, 25], [], [7, 27], [3, 5, 8, 12, 40], [4, 5, 21, 23, 47], [4, 6, 10, 14, 42], [5, 6, 23, 25, 49], [5, 7, 12, 16, 44], [6, 7, 25, 27, 51], [6, 14], [7, 27], [7, 16], [], [6, 7, 14, 16, 30, 32, 52], [5, 7, 23, 27, 35, 39, 55], [7, 16, 32], [6, 25, 37], [], [7, 27, 39], [6, 7, 14, 16, 42, 44, 56], [5, 7, 23, 27, 47, 51, 59], [7, 16, 44], [6, 25, 49], [], [7, 27, 51], [5, 7, 12, 16, 28, 32, 60], [6, 7, 25, 27, 37, 39, 63], [6, 14, 30], [7, 27, 39], [7, 16, 32], [], [5, 7, 12, 16, 40, 44, 64], [6, 7, 25, 27, 49, 51, 67], [6, 14, 42], [7, 27, 51], [7, 16, 44], [], [], [7, 27, 39, 55], [], [7, 27, 51, 59], [], [7, 27, 39, 63], [], [7, 27, 51, 67], [7, 16, 32, 52], [], [7, 16, 44, 56], [], [7, 16, 32, 60], [], [7, 16, 44, 64], []], [[2, 3, 9, 18], [3, 4, 11, 20], [4, 5, 13, 22], [5, 6, 15, 24], [6, 7, 17, 26], [8], [], [3, 5, 18, 22, 34], [4, 5, 11, 13, 29], [4, 6, 20, 24, 36], [5, 6, 13, 15, 31], [5, 7, 22, 26, 38], [6, 7, 15, 17, 33], [6, 24], [7, 17], [7, 26 ], [], [4, 5, 20, 22, 46], [3, 5, 9, 13, 41], [5, 6, 22, 24, 48], [4, 6, 11, 15, 43], [6, 7, 24, 26, 50], [5, 7, 13, 17, 45], [7, 26], [6, 15], [], [7, 17], [5, 7, 22, 26, 34, 38, 54], [6, 7, 15, 17, 31, 33, 53], [6, 24, 36], [7, 17, 33], [7, 26, 38], [], [ 5, 7, 22, 26, 46, 50, 58], [6, 7, 15, 17, 43, 45, 57], [6, 24, 48], [7, 17, 45], [7, 26, 50], [], [6, 7, 24, 26, 36, 38, 62], [5, 7, 13, 17, 29, 33, 61], [7, 26, 38], [6, 15, 31], [], [7, 17, 33], [6, 7, 24, 26, 48, 50, 66], [5, 7, 13, 17, 41, 45, 65], [7, 26, 50], [6, 15, 43], [], [7, 17, 45], [7, 26, 38, 54], [], [7, 26, 50, 58], [], [7, 26, 38, 62], [], [7, 26, 50, 66], [], [], [7, 17, 33, 53], [], [7, 17, 45, 57], [], [7, 17, 33, 61], [], [7, 17, 45, 65]], [[1, 3, 18, 19], [2, 4, 20, 21], [3, 5, 22, 23 ], [4, 6, 24, 25], [5, 7, 26, 27], [8], [8], [4, 5, 20, 22, 34], [4, 5, 21, 23, 35], [5, 6, 22, 24, 36], [5, 6, 23, 25, 37], [6, 7, 24, 26, 38], [6, 7, 25, 27, 39], [7, 26], [7, 27], [], [], [3, 5, 18, 22, 46], [3, 5, 19, 23, 47], [4, 6, 20, 24, 48], [4, 6, 21, 25, 49], [5, 7, 22, 26, 50], [5, 7, 23, 27, 51], [6, 24], [6, 25], [7, 26], [7, 27], [6, 7, 24, 26, 36, 38, 54], [6, 7, 25, 27, 37, 39, 55], [7, 26, 38], [7, 27, 39], [], [], [6, 7, 24, 26, 48, 50, 58], [6, 7, 25, 27, 49, 51, 59], [7, 26, 50], [7, 27, 51], [], [], [5, 7, 22, 26, 34, 38, 62], [5, 7, 23, 27, 35, 39, 63], [6, 24, 36], [6, 25, 37], [7, 26, 38], [7, 27, 39], [5, 7, 22, 26, 46, 50, 66], [5, 7, 23, 27, 47, 51, 67], [6, 24, 48], [6, 25, 49], [7, 26, 50], [7, 27, 51], [], [], [], [], [], [], [], [], [7, 26, 38, 54], [7, 27, 39, 55], [7, 26, 50, 58], [7, 27, 51, 59], [7, 26, 38, 62], [7, 27, 39, 63], [7, 26, 50, 66], [7, 27, 51, 67]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67])


Output

1. Input:
Automaton("nondet",96,4,[[[1, 3, 9, 10], [2, 4, 11, 12], [3, 5, 13, 14], [4, 6, 15, 16], [5, 7, 17, 18], [6, 8, 19, 20], [7 ], [8], [3, 5, 9, 13, 33], [3, 5, 10, 14, 34], [4, 6, 11, 15, 35], [4, 6, 12, 16, 36], [5, 7, 13, 17, 37], [5, 7, 14, 18, 38], [6, 8, 15, 19, 39], [6, 8, 16, 20, 40], [7, 17], [7, 18], [8, 19], [8, 20], [4, 5, 11, 13, 49], [4, 5, 12, 14, 50], [5, 6, 13, 15, 51], [5, 6, 14, 16, 52], [6, 7, 15, 17, 53], [6, 7, 16, 18, 54], [7, 8, 17, 19, 55], [7, 8, 18, 20, 56], [8, 19], [8, 20], [], [], [5, 7, 13, 17, 33, 37, 65], [5, 7, 14, 18, 34, 38, 66], [6, 8, 15, 19, 35, 39, 67], [6, 8, 16, 20, 36, 40, 68], [7, 17, 37], [7, 18, 38], [8, 19, 39], [8, 20, 40], [5, 7, 13, 17, 49, 53, 73], [5, 7, 14, 18, 50, 54, 74], [6, 8, 15, 19, 51, 55, 75], [6, 8, 16, 20, 52, 56, 76], [7, 17, 53], [7, 18, 54], [8, 19, 55], [8, 20, 56], [6, 7, 15, 17, 35, 37, 81], [6, 7, 16, 18, 36, 38, 82], [7, 8, 17, 19, 37, 39, 83], [7, 8, 18, 20, 38, 40, 84], [8, 19, 39], [8, 20, 40], [], [], [6, 7, 15, 17, 51, 53, 89], [6, 7, 16, 18, 52, 54, 90], [7, 8, 17, 19, 53, 55, 91], [7, 8, 18, 20, 54, 56, 92], [8, 19, 55], [8, 20, 56], [], [], [7, 17, 37, 65], [7, 18, 38, 66 ], [8, 19, 39, 67], [8, 20, 40, 68], [7, 17, 53, 73], [7, 18, 54, 74], [8, 19, 55, 75], [8, 20, 56, 76], [7, 17, 37, 81], [7, 18, 38, 82], [8, 19, 39, 83], [8, 20, 40, 84], [7, 17, 53, 89], [7, 18, 54, 90], [8, 19, 55, 91], [8, 20, 56, 92], [8, 19, 39, 67], [8, 20, 40, 68], [], [], [8, 19, 55, 75], [8, 20, 56, 76], [], [], [8, 19, 39, 83], [8, 20, 40, 84], [], [], [8, 19, 55, 91], [8, 20, 56, 92], [], []], [[2, 3, 9, 22], [3, 4, 11, 24], [4, 5, 13, 26], [5, 6, 15, 28], [6, 7, 17, 30], [7, 8, 19, 32], [8 ], [], [4, 5, 11, 13, 33], [3, 5, 22, 26, 42], [5, 6, 13, 15, 35], [4, 6, 24, 28, 44], [6, 7, 15, 17, 37], [5, 7, 26, 30, 46], [7, 8, 17, 19, 39], [6, 8, 28, 32, 48], [8, 19], [7, 30], [], [8, 32], [3, 5, 9, 13, 49], [4, 5, 24, 26, 58], [4, 6, 11, 15, 51], [ 5, 6, 26, 28, 60], [5, 7, 13, 17, 53], [6, 7, 28, 30, 62], [6, 8, 15, 19, 55], [7, 8, 30, 32, 64], [7, 17], [8, 32], [8, 19], [], [6, 7, 15, 17, 35, 37, 65], [5, 7, 26, 30, 42, 46, 70], [7, 8, 17, 19, 37, 39, 67], [6, 8, 28, 32, 44, 48, 72], [8, 19, 39], [7, 30, 46], [], [8, 32, 48], [6, 7, 15, 17, 51, 53, 73], [5, 7, 26, 30, 58, 62, 78], [7, 8, 17, 19, 53, 55, 75], [6, 8, 28, 32, 60, 64, 80], [8, 19, 55], [7, 30, 62], [], [8, 32, 64], [5, 7, 13, 17, 33, 37, 81], [6, 7, 28, 30, 44, 46, 86], [6, 8, 15, 19, 35, 39, 83], [7, 8, 30, 32, 46, 48, 88], [7, 17, 37], [8, 32, 48], [8, 19, 39], [], [5, 7, 13, 17, 49, 53, 89], [6, 7, 28, 30, 60, 62, 94], [6, 8, 15, 19, 51, 55, 91], [7, 8, 30, 32, 62, 64, 96], [7, 17, 53], [8, 32, 64], [8, 19, 55], [], [8, 19, 39, 67], [7, 30, 46, 70], [], [8, 32, 48, 72], [8, 19, 55, 75], [7, 30, 62, 78], [], [8, 32, 64, 80], [8, 19, 39, 83], [7, 30, 46, 86], [], [8, 32, 48, 88], [8, 19, 55, 91], [7, 30, 62, 94], [], [8, 32, 64, 96], [7, 17, 37, 65], [8, 32, 48, 72], [8, 19, 39, 67], [], [7, 17, 53, 73], [8, 32, 64, 80], [8, 19, 55, 75], [], [7, 17, 37, 81], [8, 32, 48, 88], [8, 19, 39, 83], [], [7, 17, 53, 89], [8, 32, 64, 96 ], [8, 19, 55, 91], []], [[2, 3, 10, 21], [3, 4, 12, 23], [4, 5, 14, 25], [5, 6, 16, 27], [6, 7, 18, 29], [7, 8, 20, 31], [8], [], [3, 5, 21, 25, 41], [4, 5, 12, 14, 34], [4, 6, 23, 27, 43], [5, 6, 14, 16, 36], [5, 7, 25, 29, 45], [6, 7, 16, 18, 38], [6, 8, 27, 31, 47], [7, 8, 18, 20, 40], [7, 29], [8, 20], [8, 31], [], [4, 5, 23, 25, 57], [3, 5, 10, 14, 50], [5, 6, 25, 27, 59], [ 4, 6, 12, 16, 52], [6, 7, 27, 29, 61], [5, 7, 14, 18, 54], [7, 8, 29, 31, 63], [6, 8, 16, 20, 56], [8, 31], [7, 18], [], [8, 20 ], [5, 7, 25, 29, 41, 45, 69], [6, 7, 16, 18, 36, 38, 66], [6, 8, 27, 31, 43, 47, 71], [7, 8, 18, 20, 38, 40, 68], [7, 29, 45], [8, 20, 40], [8, 31, 47], [], [5, 7, 25, 29, 57, 61, 77], [6, 7, 16, 18, 52, 54, 74], [6, 8, 27, 31, 59, 63, 79], [7, 8, 18, 20, 54, 56, 76], [7, 29, 61], [8, 20, 56], [8, 31, 63], [], [6, 7, 27, 29, 43, 45, 85], [5, 7, 14, 18, 34, 38, 82], [7, 8, 29, 31, 45, 47, 87], [6, 8, 16, 20, 36, 40, 84], [8, 31, 47], [7, 18, 38], [], [8, 20, 40], [6, 7, 27, 29, 59, 61, 93], [5, 7, 14, 18, 50, 54, 90], [7, 8, 29, 31, 61, 63, 95], [6, 8, 16, 20, 52, 56, 92], [8, 31, 63], [7, 18, 54], [], [8, 20, 56], [7, 29, 45, 69], [8, 20, 40, 68], [8, 31, 47, 71], [], [7, 29, 61, 77], [8, 20, 56, 76], [8, 31, 63, 79], [], [7, 29, 45, 85], [8, 20, 40, 84], [8, 31, 47, 87], [], [7, 29, 61, 93], [8, 20, 56, 92], [8, 31, 63, 95], [], [8, 31, 47, 71], [7, 18, 38, 66], [], [8, 20, 40, 68], [8, 31, 63, 79], [7, 18, 54, 74], [], [8, 20, 56, 76], [8, 31, 47, 87], [7, 18, 38, 82], [], [8, 20, 40, 84], [8, 31, 63, 95], [7, 18, 54, 90 ], [], [8, 20, 56, 92]], [[1, 3, 21, 22], [2, 4, 23, 24], [3, 5, 25, 26], [4, 6, 27, 28], [5, 7, 29, 30], [6, 8, 31, 32], [8], [8], [4, 5, 23, 25, 41], [4, 5, 24, 26, 42], [5, 6, 25, 27, 43], [5, 6, 26, 28, 44], [6, 7, 27, 29, 45], [6, 7, 28, 30, 46], [7, 8, 29, 31, 47], [7, 8, 30, 32, 48], [8, 31], [8, 32], [], [], [3, 5, 21, 25, 57], [3, 5, 22, 26, 58], [4, 6, 23, 27, 59], [4, 6, 24, 28, 60], [5, 7, 25, 29, 61], [5, 7, 26, 30, 62], [6, 8, 27, 31, 63], [6, 8, 28, 32, 64], [7, 29], [7, 30], [8, 31], [8, 32], [6, 7, 27, 29, 43, 45, 69], [6, 7, 28, 30, 44, 46, 70], [7, 8, 29, 31, 45, 47, 71], [7, 8, 30, 32, 46, 48, 72], [8, 31, 47], [8, 32, 48], [], [], [6, 7, 27, 29, 59, 61, 77], [6, 7, 28, 30, 60, 62, 78], [7, 8, 29, 31, 61, 63, 79], [7, 8, 30, 32, 62, 64, 80], [8, 31, 63], [8, 32, 64], [], [], [5, 7, 25, 29, 41, 45, 85], [5, 7, 26, 30, 42, 46, 86], [6, 8, 27, 31, 43, 47, 87], [6, 8, 28, 32, 44, 48, 88], [7, 29, 45], [7, 30, 46], [8, 31, 47], [8, 32, 48], [5, 7, 25, 29, 57, 61, 93], [5, 7, 26, 30, 58, 62, 94], [6, 8, 27, 31, 59, 63, 95], [6, 8, 28, 32, 60, 64, 96], [7, 29, 61], [7, 30, 62], [8, 31, 63], [8, 32, 64], [8, 31, 47, 71], [8, 32, 48, 72 ], [], [], [8, 31, 63, 79], [8, 32, 64, 80], [], [], [8, 31, 47, 87], [8, 32, 48, 88], [], [], [8, 31, 63, 95], [8, 32, 64, 96 ], [], [], [7, 29, 45, 69], [7, 30, 46, 70], [8, 31, 47, 71], [8, 32, 48, 72], [7, 29, 61, 77], [7, 30, 62, 78], [8, 31, 63, 79], [8, 32, 64, 80], [7, 29, 45, 85], [7, 30, 46, 86], [8, 31, 47, 87], [8, 32, 48, 88], [7, 29, 61, 93], [7, 30, 62, 94], [8, 31, 63, 95], [8, 32, 64, 96]]],[1],[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96])

1. The DFA for 7 plus the NFAs/DFAS for 8, 9, 10, 11 are here as they are too big to paste. For 12, 13, 14, 15 I have only included the NFAs. The files have names k6dfa, k7nfa, k7dfa etc. As an example, the input for problem 7 is k7nfa and the output is k7dfa. Hopefully the rest of the names are clear. If your code is correct for problems 1-11, I am happy to believe it is correct in general.

# Score

I will time your code on test cases 1..15 from above of increasing size. Your score will be the largest test case your code can process in less than 10 minutes. If two answers get to the same size then the one that is fastest on that largest test case wins. The test machine is an Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz. You can use at most 16 of its cores.

# Testing

I will check your answers (for the smaller cases) using AreEquivAut .

[Thank you to Christian Sievers for the example NFAs.]

• What does "the largest test case" mean? Does this task really have no pathological and trivial cases? – the default. Apr 21 '20 at 14:33
• @mypronounismonicareinstate Thanks for reading the draft so far! I should number the cases but it means, considering the inputs in the order I have given them (there will be more once I work out where I can upload them to), stop at the first one that takes more than 10 minutes using your code. The one just before is the largest one. Does that make sense? – user9207 Apr 21 '20 at 14:59
• I was not able to actually read the draft, as the only thought the words "DFA" and "NFA" induce in my mind is "something complicated related to regex". – the default. Apr 21 '20 at 15:01
• @mypronounismonicareinstate ah. They are really much simpler. I will include some pictures and a description too. You can think of DFAs as a really simple programming language. But do you know where I can upload a 30MB text file to link to? Or a 6MB compressed file – user9207 Apr 21 '20 at 15:03
• (I can also understand the words "deterministic/nondeterministic finite automaton", but I have no idea how to use them to do anything useful other than simply applying them) I guess I don't know. (didn't want to simply leave you waiting for an answer indefinitely) – the default. Apr 21 '20 at 15:07
• So the output doesn't need to be minimal and just needs to be equivalent to the expected output, right? (Guessing so because the example at the top could have been Automaton("det", 1, 2, [[1], [1]], [1], []) if I'm understanding the syntax correctly) And there's a redundant [3] in the example input NFA, and you need to format the test inputs as code because plain [1]s and [2]s are messing up with Markdown. – Bubbler Apr 21 '20 at 23:50
• @Bubbler Thank you for reading it! I have updated the question. Please let me know if there are any other problems. – user9207 Apr 22 '20 at 8:44
• Some are still not fixed: example input NFA's [3], test case 1's input is not code-blocked, and test case 2's output is lost. – Bubbler Apr 23 '20 at 2:22
• @Bubbler Hopefully all fixed now. – user9207 Apr 23 '20 at 10:51

# Improved image sampling popularity-contestgraphical-outputimage-processing

Quoting from the ImageMagick documentation of the very simple -sample resizer, "You can think of the image as being divided into an array of regions, and one pixel from each region is selected for the resulting image". Unfortunately, it uses a bad algorithm for choosing the one pixel: it chooses the middle one.

In this challenge, you have to write a program that takes an image and a positive integer $$\N\$$ ($$\N\$$ divides the height and the width) as input and outputs the image downscaled by the factor $$\N\$$. In the output image, every pixel must be taken from the corresponding $$\N\times N\$$ square in the original image.

[image gallery and settings used]

This is tagged , so the answer with the most upvotes wins!

# Fetch me some data internetcode-golfcode-challenge

This is the fifth post for the second RGS's Golfing Showdown.

Write some code to fetch the updated total number of confirmed infected cases in a territory. The territory you choose to fetch data for will influence your score, so keep that in mind.

# Output

You should output an integer or any other sensible representation of it.

# Rules

## Fetching the data

The data you fetch must be fetched from a URI that must have been online at least since the 25th of April of 2020. You may fetch the most recent data or the data for a specific date, as long as in that date, your territory has a non-zero number of total confirmed cases.

## Scoring and Territory

The territory you fetch data for must be a territory listed in the WHO daily situation reports and the numbers you fetch for a given date must be within 10% of the WHO numbers for the same date.

Your score will be the number of bytes minus the length of the longest common substring between your code and the territory you pick, case insensitive.

E.g. If my program is abcdefghijklmno and my territory is Italy I get to shave 2 bytes of my score because of the common substring il (or al).

# Sandbox

Are the rules clear enough and well-specified enough?

• I understand now, I think. I read "The territory you choose to fetch data for will influence your score, so keep that in mind." and assumed that you meant that the size of the data we fetch will be part of our score. You should probably make it explicit that the size of any file fetched won't be part of our score if that's what you intend. – S.S. Anne Apr 29 '20 at 19:16
• "Your score will be the number of bytes minus the length of the longest common substring between your code and the territory you pick, case insensitive." Are you trying to do this so, say, wget Italy will be the same size as wget UnitedStates? I think instead you should make it a requirement that the name of your territory is included in your program, and then remove the number of bytes in your territory name. – S.S. Anne Apr 29 '20 at 19:17
• The number of confirmed cases in China has almost stopped increasing. Can we assume it won't increase by 10% and thus create an offline solution? – the default. Apr 30 '20 at 0:41
• Can we require inputs to be padded for us? – user92069 Apr 17 '20 at 8:14
• Can we output via a digit array? – user92069 Apr 17 '20 at 8:14
• What do you mean by output via a digit array? Like [2,4] instead of 24? – Command Master Apr 17 '20 at 8:36
• What do you mean by Are you sure you mean base 19, not base 10?? In base 10 16 isn't a digit, and [1, 16] isn't a number – Command Master Apr 17 '20 at 8:38
• Why base 19? That seems pretty arbitrary – xnor Apr 17 '20 at 8:40
• It's the smallest base for which the sum of any two digits in base 10 fit in – Command Master Apr 17 '20 at 8:41
• Looks like a cool challenge :) I think a few more test cases would be useful. Some slightly larger test cases would also be great – math junkie Apr 26 '20 at 19:46
• I doubt that there is any approach other than "take the decimal digits, sum the digits as vectors and convert from base 19" here. – the default. May 1 '20 at 2:43

This is my first question, so I don't know what exactly I should ask, but I will try. Please advise.

# Russian roulette

It's Russian roulette! The rules are simple. Shoot a revolver with n slots for bullets and one round inside at your head and you might not die!

Make a program that takes integer n (you can assume that 10<=n<=128) as input and outputs nothing.

but how do I tell if I'm dead?

The program generates a random number x in the range 0 - (n) inclusive. If x=n the revolver fires and the program exits with an error (you die). Otherwise the program exits normally.

Standard loopholes forbidden, etc.

Sandbox questions:

• This question is short. What can I explain better or add?
• What are good tags to add?
• Should I make it code-golf or popularity contest? Both?
• Too easy?
• This is a joke, will it be misinterpreted?
• So do we choose our own value for n, or is there some value you want us to use. – lyxal May 2 '20 at 3:00
• I think this challenge is extremely similar to this one: Make your code error but only sometimes – math junkie May 2 '20 at 3:20
• @mathjunkie I saw that, but this question is more specific for how it should function. – Wzl May 2 '20 at 18:10
• @Lyxal Originally I thought I'd let the answerers choose, but to make the question different from Make your code error but only sometimes I'll revise the question to take n from the player. – Wzl May 2 '20 at 18:12
• is that 0-n or 1-n inclusive, exclusive, or half-open? Also, some languages give error messages when they exit with failure. – S.S. Anne May 2 '20 at 18:24
• @S.S.Anne I meant to say you can choose. Fixing. – Wzl May 2 '20 at 18:27
• I don't think allowing to choose is a good idea. If anything, I would prefer 0-(n-1), as that is the most common and easiest to work with. – S.S. Anne May 2 '20 at 18:33
• I suggest tagging it code-golf instead of popularity-contest because popcons are netoriously difficult to do right. – lyxal May 3 '20 at 1:14
• Pseudocode of (likely) most answers you will get: 1/(rand()%n); – the default. May 3 '20 at 3:33
• @lyxal but maybe I should make it popularity-contest and encourage people to vote for ones that do not follow 1/(rand()%n)? – Wzl May 4 '20 at 13:55
• posted – Wzl May 4 '20 at 15:29

## Revisit sum

Why is this language specific?

As much as much as I like challenges to be language agnostic if this challenge were language agnostic it would most certainly be a duplicate of the add two numbers challenge due to our current duplicate policy. And for most languages adding two numbers and adding several numbers are no different. Revisit is not one of those languages.

In Revisit adding two numbers is easy.

+@


does the trick. However in this challenge we are going to ask you to do something much more difficult. Take a an arbitrary number of positive integers as input and output the sum of all them.

This is so answers are scored in bytes with fewer bytes being better.

# Compass and straightedge segment reduction code-golfgeometry

You are given two points at distance 1, a compass and a straightedge. The challenge is, given a positive integer $$\N\$$, to find the shortest segment possible to obtain by drawing no more than $$\N\$$ lines or circles. A segment is defined as a pair of two points such that there is a line connecting them.

This is tagged , so the shortest answer wins!

## Sandbox stuff

• Certain details of compass-and-straightedge constructions are not specified yet.

• Should I allow assuming normal floating point math to be exact, or to require proper arbitrary precision?

• Is the answer trivial? I know that you can, for example, obtain geometric progressions with factor that seems to be $$\\tan(x)\$$ (and thus perhaps it's optimal to first bisect an angle for a while, then subtract it from a straight angle, and then do this).

More importantly, is this possible? I assume it is, because it seems possible to calculate everything necessary for the basic constructions:

• It's (easily) possible to compare lines and circles for equality
• It's possible to calculate the parameters of a line passing through 2 points.
• It's possible to calculate the parameters of a circle - that is, find the point and the radius given the point and the radius.
• It's possible to calculate the point of intersection between 2 lines (if it exists).
• It's possible to calculate the points of intersection between a line and a circle.
• It's possible to calculate the points of intersection between 2 circles.

Is that enough for a proof?

# Continue an arithmetic-geometric progression code-golfmath

note: not related to these arithmetic-geometric sequences
An arithmetic progression has the property that $$\a_n = \frac{a_{n-1} + a_{n+1}}2\$$ - that is, every term is the arithmetic mean of its neighbours.
A geometric progression has a similar property: $$\a_n = \root\of{a_{n-1}\cdot a_{n+1}}\$$ - every term is the geometric mean of its neighbours.

There's also the arithmetic-geometric mean $$\AGM(x, y)\$$! It's defined as follows: define two sequences as $$\a_0 = x, g_0 = y, a_{n+1} = \frac{a_n+g_n}2, g_{n+1}=\root\of{a_n g_n}\$$. The sequences converge to the same number, the arithmetic-geometric mean of $$\x\$$ and $$\y\$$.

Now I can define another progression: an arithmetic-geometric progression has the property that $$\a_n = AGM(a_{n-1}, a_{n+1})\$$.

As input you are given two real numbers - the first two terms of an arithmetic-geometric progression. The challenge is to find the third one with absolute or relative error not exceeding $$\10^{-5}\$$ (and output it).

This is tagged , so the shortest answer wins!

# Emulate a Schmitt trigger

Given low and high cutoff points, and a list of input readings, generate a list of output states at those points.

• If an input reading is greater than the high cutoff point then the output is always in the high cutoff state.
• If an input reading is lower than the low cutoff point then the output is always in the low cutoff state.
• At least one of the above comparisons must be a strict inequality. (Please make both comparisons strict unless this would consume additional bytes.)
• If the initial reading is between the two cutoff points the the output must be deterministic (i.e. the same for each run with the same inputs).
• In all other cases the output remains in the same state.
• It is valid for both cutoff points to be the same value.
• The input readings may be taken in any convenient format, but it must be capable of handling at least 94 different values.
• The output for each input reading must be one of two distinct values.

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

# Subtract a list code-golf

You are given a list of boolean values as input. You have to find its difference.

The difference of a list of one value is equal to the value itself. The difference of a list with $$\N\$$ values is defined as $$(\text{the difference of the first }\lfloor\frac{N}2\rfloor\text{ items}) - (\text{the difference of the last }\lceil\frac{N}2\rceil\text{ items})$$

This is tagged , so the shortest answer wins!

[todo: examples]

# Analyze the flow

Posted

• From the example, it looks like the path can wrap around the edges of the grid. I think you should mention that explicitly. I also think you should define "tributary" – math junkie May 11 '20 at 21:27
• Yes, you can wrap around and this is the only reason why I use a toroidal grid. I've added the definition of "tributary"... I know it's still informal but I don't want to lose readability, I've tried to go more formal but the need of a lot of definitions arises. Is it still unclear? – Domenico Modica May 12 '20 at 0:36
• @math junkie anyway thanks for the grammar corrections, also in the main post :D – Domenico Modica May 13 '20 at 19:42

There are $$\a\$$ honest man(always tell the truth), $$\b\$$ dishonest man(always tell lie), and $$\c\$$ random man(tell random Y/N). How many times at least should you ask one of them a yes/no question to guarantee you get knowledge of who they are? You may assume that it's possible.

Test cases:

(a,b,c) -> ans
(1,1,0) -> 1
(1,1,1) -> 3
(0,0,2) -> 0


Notes:

• I don't know if there's clever way, but anyway brute-force work
• Actually it's possible to identify them iff there are less than half of random answerer, or an edge case that all are random answerers. Only considering honest and random, if there are more honest than random, ask them same question and do a majority vote gets answer to the question. If there are same honest and random, and random tell as if they are honest and real honest are random, you can't tell the difference.
• I think the wording is a little confusing. Will there always be one of each? Will your program be given a list of a, b, and cs as input? Also, you may want to look at this question to check if it's similar to yours. – Redwolf Programs May 14 '20 at 21:23
• @RedwolfPrograms Yes a,b,c are given, and possibly zero. Link don't match this problem well – l4m2 May 15 '20 at 2:48
• Wouldn't it require at least 4 questions for the test case (1, 1, 1)? How to solve in 3? – user202729 May 16 '20 at 3:46
• @user202729 brainden.com/forum/topic/… (not wiki answer as it assume answer from random is either true or false) – l4m2 May 16 '20 at 3:47
• Oh wiki also has a standard solution – l4m2 May 16 '20 at 3:53
• – user202729 May 16 '20 at 4:48

The game of scrabble is played by placing lettered tiles on a grid to form words. The words being formed must read from left to right, or up to down on the grid. The words must appear in the official Scrabble dictionary, and all letters placed on the grid must be part of a valid word. This challenge will focus on a specific technique for playing a simplified version of Scrabble.

A useful technique when playing Scrabble is to add a single letter to an existing word that is already on the board to form a new word. Write a program or function that, when given a dictionary, finds the longest series of words that can be formed by adding a single letter to another word to form a new word.

## Example

You are given the following dictionary:

at
ate
rate
elate
crate
belate
belated


['at', 'ate', 'rate', 'crate']


An invalid output would be:

['at', 'ate', 'elate', 'belate', 'belated']


because 'elate' cannot be formed by adding a single letter to 'ate'.

Note that this challenge is not about finding the longest word that can be formed by adding a single letter to another word, but about finding the longest chain of words that can be formed in such a way. Which means that this answer:

['elate', 'belate', 'belated']


is wrong, because it only has three steps, whereas the first example has four.

## Winning Criteria

Code-golf, so shortest code wins. I/O is flexible. Standard loopholes apply. Take dictionary as a list, file, delimited string, or whatever you want. Output can be sent to stdout, returned as a single string (with delimiter), or list of strings.

TODO

# Uniform necklace sampling code-challengerandom

The challenge is, given a number $$\N\$$, to produce a random binary necklace of length $$\N\$$. All possible necklaces must have the same probability of being chosen.

## Scoring

Solutions are compared first by asymptotic memory complexity in $$\N\$$ (lower is better), and, in case of a tie, by size (lower is better).

## Sandbox stuff

(I do intend to use code-golf as only a tiebreaker)

• How to tag this question the most correctly?
• Not time complexity? It's trivial to do this in O(n) memory (I think that is optimal, because (as far as I know) it's not possible to (deterministically) check if a string is a necklace in less memory) by iterating over all necklaces, count number of those = C (C can be represented in N bits), generate a random number x in the range 1..C, then count again and pick the xth necklace. – user202729 May 27 '20 at 4:10
• @user202729 I tried to pick a combinatorial object that prevents a linear-memory solution (any suggestions?). I guess these answers should win (with [code-golf] used to compare them - this is mostly [restricted-memory] code-golf, but submissions that aren't good enough aren't disqualified). – the default. May 27 '20 at 6:44
• What happens if the specified table doesn't exist? – lyxal May 15 '20 at 4:37
• The usual SQL statement is SELECT * FROM data, where * is the wildcard operator. Also, the set of parentheses after "WHERE" is not mandatory in usual SQL. I guess these changes make the challenge easier to parse. – user92069 May 15 '20 at 4:56
• @Λ̸̸ Yeah, it's to make it slightly easier. However, I could change it. Which I will! – bigyihsuan May 15 '20 at 23:54
• @Lyxal undefined, the programs should assume that the table is in the database – bigyihsuan May 15 '20 at 23:55
• Consider deleting this post, as the challenge is already on main – RGS May 20 '20 at 16:50

# Solve some diplomatic issues

You are given a set of moves in a theoretical Diplomacy game. We're not going to handle validation of moves being legal or not, simply attempt to resolve a turn.

Here are the simplified rules to Diplomacy (full rules here):

• There are two types of units: Armies and Fleets. Armies can only move on land, Fleets on land and in the sea. You can safely ignore this, because we're assuming that all of the moves you've been given are at least theoretically valid.
• There are four types of moves: Hold (stay in place), Move, Support (a certain other unit), Convoy.
• When two or more units end up in the same country, whichever unit has the most support stays. Each unit without the most support (or each unit tied for the most) returns to its original country. A unit which is not Moving and which is not tied for the most support is Dislodged.
• A Fleet can Convoy an Army through its space to another space. That convoy is cancelled if the Fleet is Dislodged. Only a Fleet in a sea space can Convoy.
• A unit can support another unit holding or moving into an adjacent country if it can move into that country (Armies can't Support Fleets in the sea).
• A supporting unit which is attacked ceases to support, unless it is supporting an attack on the unit attacking it. If it is dislodged, it ceases to support in any case.
• The Beleaguered Garrison rule: If a unit is attacked by two units with the same amount of support, the attacked unit is not Dislodged, and the attackers return to their original countries.

You will receive a list of moves. Each move will be in the following format:

Power Unit_type Origin_country Move_type Destination_country


There is no Destination_country if a unit holds (or you can insert a placeholder). Destination_country for Support or Convoy is the Origin_country of the unit being Supported or Convoyed. For example, you could get:

E F Eng M Pic
F A Pic H
G A Bel S Eng


This means:

English Fleet in the English Channel Moves to Picardy
French Army in Picardy Holds
German Army in Belgium Supports the Fleet in the English Channel to Move to Picardy


Your output should be the location of each unit after the move. Any Dislodged unit should be marked as such.

# Output format:

Power Unit_type Country Dislodged?


For the example given above, the output should be:

E F Pic
F A Pic D
G A Bel


The more difficult part of this is in regards to convoys. A convoy fails if there is no valid path for the army to take. For instance, if we have:

E F Nth C Den
E A Den M Hol
F F Eng M Nth
F F Bel S Eng


The French fleets dislodge the English Fleet in the North Sea, and the convoy does not take place. But if we also had

E F Hel C Den


There would still be a valid path for the English Army and the convoy would succeed.

Be warned, there are paradoxes in Diplomacy. These are to be treated as undefined behaviour; any output is acceptable where

1. Each unit is listed
2. There is only one non-dislodged unit per country
3. In any country with a dislodged unit there is a non-dislodged unit
4. Each non-moving unit is listed in its origin country
5. Each moving unit is listed either in its origin country or its destination country

Note that, in particular, each unit being in its starting country is a valid output.

For use with convoys, it's helpful to know which countries are adjacent to which other countries. (Everything is assumed to be valid, but it may not be clear whether a convoy with a single cut link is still possible otherwise).

You may assume that this list is available to you in any format: a function that takes two countries and returns true/false, a variable, a file, etc. In any case, the list itself does not add to your byte count.

# Input/Output Formats

You can use any Input/Output formats you choose, as is standard.

# Questions for the sandbox

• How much clearer does my description of the rules of Diplomacy need to be?
• Does this sound like an interesting challenge?

# Enforce Social Distancing! code-challengetest-battery

Related to Maintain Social Distancing!.

As in that challenge, there is a 2-dimensional array of 1s and 0s representing people. In it, social distancing is maintained if and only if all 1s are at least 6 squares apart, where distance metric used is $$\|\Delta x| + |\Delta y|\$$ (rectilinear or Manhattan).

The challenge here is to move some people in a given 2D array so that social distancing is maintained. It's guaranteed that it's possible to do so. Your program's score on a given input is the total distance moved by all people.

Your program's running time must not exceed 10 seconds on any of the test cases.

This is tagged , so there is a large set of inputs your programs will be tested on [TODO: actually create it]. The program with the lowest total score on all of these inputs wins.

## Sandbox stuff

• Is this currently a bad idea for the reasons specified by Shaggy in the following comment?

I am sorry but I have downvoted this for what others may perceive to be a trivial reason: Code Golf is one of the few things I have left where I can escape how fucked my world has become; I absolutely do not want to come here to be reminded that I can't hug my family and friends.

• Is there an optimal algorithm? (I hope not)