490
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| |
\$\endgroup\$

2972 Answers 2972

1
85 86
87
88 89
100
0
\$\begingroup\$

chaining couples with parity

Rules

Take the \$n\$ first integers (with 0 included or not) with \$n\$ an even number except 0.

The goal is to produce a (not so) random chain of couples with these numbers, for example with \$n=6\$ : (5, 4), (1, 6), (3, 2)

But you have to respect a bit of parity and randomness :

  1. Each second number in a couple must have the same parity than the first number of the next couple. No rule for the first number of the first couple and the second number of the last couple. So the example above is not a correct answer.

(5, 4), (6, 1), (3, 2) is a correct answer for \$n=6\$.

So this is a sort of parity chain.

  1. First number (of the first couple) has to be chosen randomly (uniform) in the \$n\$ first integers.

Input

An even number \$n\$ greater or equal than 2.

Valid output examples

  • Input: \$n=2\$ Outputs (1, 2) and (2, 1) are valid. (0, 1) and (1,0) are also.

  • Input: \$n=4\$ Output: (0, 1), (3, 2) (if start with 0) because 1 and 3 are odd

  • Input: \$n=4\$ Output: (1, 4), (2, 3) (if start with 0)

  • Input: \$n=6\$ Output: (0, 5), (1, 3), (4, 2)

  • Input: \$n=8\$ Output: (6, 7), (1, 0), (2, 5), (3, 4)

Invalid output examples

  • Input: \$n=4\$ Output:(1, 2), (3, 4) because 2 is even and 3 is odd.

  • Input: \$n=6\$ Output:(5, 4), (1, 6), (3, 2) because 4 is even and 1 is odd and also because 6 is even and 3 is odd.

What if \$n\$ is odd?

No rule for \$n\$ if it's odd. All outputs accepted!

What about output's format?

No special formatting is expected. You just have to separate the couples such that one can correctly see them.

Sandbox Questions

Duplicate?

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ Use \$ instead of $ to use MathJax. Also, what do you exactly want by "random"? Is it acceptable to pick from two answers (e.g. pick between (1 2)(4 3)(5 6) and (5 6)(4 3)(1 2))? Check this and this. \$\endgroup\$ – Bubbler Apr 8 at 1:43
  • \$\begingroup\$ @Bubbler Thx. I tried to be clearer about randomness expectations. \$\endgroup\$ – david Apr 11 at 12:58
  • \$\begingroup\$ "First number (of the first couple) has to be chosen randomly (uniform) in the n first integers." It is still easier than having to pick from all possible answers. No problem if you intended it though. \$\endgroup\$ – Bubbler Apr 12 at 23:46
0
\$\begingroup\$

Rot1Rot3

Write a program or function such that given a string \$ S \$, encode it with Rot1Rot3. To encode it, do the following:

  1. Take \$ S\$ and partition it into blocks with \$ 3 \$ characters each. If it does not partition equally (i.e. \$ |S| \bmod 3 \neq 0 \$), take away some characters from the end of the string until it does, and form a smaller partition from the 'taken-away' characters.

  2. For each individual partition, rotate it to the right by \$ 1 \$ step.

  3. Finally, rotate all of the partitions together to the right by \$ 3 \$ steps, as if each partition were one character.

Example

Input: Hello, code golf!

  1. Partition it like so: |Hel|lo,| co|de |gol|f!| (pipes to show separation). Notice that f! does not form a full partition, and is therefore left as a partition with \$ 2 \$ characters instead.

  2. Rotate each individual partition to the right by \$ 1 \$ step: |lHe|,lo|o c| de|lgo|!f|.

  3. Rotate the partitions as a whole to the right by \$ 3 \$ steps: | de|lgo|!f|lHe|,lo|o c|.

Final Output: delgo!flHe,loo c

Additional Info

  • You can expect any sequence of any characters, as long as they are printable.
  • This is , so the shortest code in bytes wins.

Test Cases

Input

Hello, code golf!
flog yhcrana
Rot1Rot3
abababa
import this
1
21
All animals are equal, but some animals are more equal than others.

Output

 delgo!flHe,loo c
yg rhcaanofl
tRoo1R3t
aabbbaa
torh tsipim
1
12
hotser.lAln aaim lsearq eluab,  utmsoae mnisalr ame eorq eluah t an
| |
\$\endgroup\$
0
\$\begingroup\$

Check my Knight's Tour

Given as input an n-by-n matrix of integers, check that all integers from 1 to are present, and that all pairs of consecutive integers are exactly a Knight's move apart. (For instance, a 4-by-4 board with the values

1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1

would meet the condition that all 1s would have a 2 that was exactly a Knight's move away, but this would of course not constitute a Knight's Tour.) The integers 1 and do NOT need to be a Knight's move apart. You must be able to support at least 7 different values for n including 10.

A Knight's move is possible between any two squares that are a Euclidean distance of √5 apart.

Output follows normal rules.

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

| |
\$\endgroup\$
  • \$\begingroup\$ I think your example would be clearer if you showed the matrix with the columns vertically stacked. It took me a while to figure out what the example was showing as is. \$\endgroup\$ – FryAmTheEggman Apr 12 at 5:03
  • \$\begingroup\$ @FryAmTheEggman My MathJax isn't good enough for that, sadly. Feel free to change all of my backquotes to backslashed dollar signs. \$\endgroup\$ – Neil Apr 12 at 9:25
  • \$\begingroup\$ Maybe you can add more test-cases \$\endgroup\$ – Command Master Apr 12 at 9:54
0
\$\begingroup\$

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.

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

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.

| |
\$\endgroup\$
  • \$\begingroup\$ I fail to see how this is a bracket. \$\endgroup\$ – infinitezero Apr 13 at 6:39
  • \$\begingroup\$ 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. \$\endgroup\$ – the default. Apr 13 at 15:47
  • \$\begingroup\$ @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. \$\endgroup\$ – Wheat Wizard Apr 13 at 15:55
  • \$\begingroup\$ @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. \$\endgroup\$ – Wheat Wizard Apr 13 at 16:04
  • \$\begingroup\$ 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.) \$\endgroup\$ – Bubbler Apr 14 at 0:08
0
\$\begingroup\$

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

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.

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

Euler's Geometry Puzzle

posted

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Apr 12 at 5:00
  • \$\begingroup\$ Thanks for the suggestion. @FryAmTheEggman I'm not sure if I can give a good definition, so I linked the pages in wolfram mathworld. \$\endgroup\$ – newbie Apr 12 at 5:36
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Apr 12 at 15:37
  • \$\begingroup\$ Done. Thanks! @FryAmTheEggman \$\endgroup\$ – newbie Apr 12 at 15:46
  • \$\begingroup\$ 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". \$\endgroup\$ – the default. Apr 13 at 15:44
  • \$\begingroup\$ 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 \$\endgroup\$ – newbie Apr 13 at 15:46
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Apr 13 at 16:01
  • \$\begingroup\$ 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) \$\endgroup\$ – newbie Apr 13 at 16:12
  • \$\begingroup\$ @newbie For what it's worth, here's what a mildly golfed formula for d alone looks like: Try it online! \$\endgroup\$ – xnor Apr 13 at 21:55
  • \$\begingroup\$ Thanks! I did some more golf and it's 66 bytes now. Would it be a better idea to output say \$R+r+d\$? \$\endgroup\$ – newbie Apr 14 at 1:29
  • \$\begingroup\$ Alright, I would go with output \$d\$. \$\endgroup\$ – newbie Apr 14 at 4:08
0
\$\begingroup\$

posted

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

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())

| |
\$\endgroup\$
  • \$\begingroup\$ What's the scoring mechanism? Code Golf I assume? \$\endgroup\$ – math junkie Apr 24 at 18:34
0
\$\begingroup\$

Finitly inverese in base N

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, ...]
| |
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – the default. Apr 16 at 10:31
  • \$\begingroup\$ I'm not sure, but from what I've seen it seems like it \$\endgroup\$ – Command Master Apr 16 at 12:33
0
\$\begingroup\$

This Question Has _____ Views

posted

| |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Command Master Apr 16 at 7:59
  • \$\begingroup\$ @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. \$\endgroup\$ – izlin Apr 16 at 8:48
  • 1
    \$\begingroup\$ someone can register a domain which will retrive the live number \$\endgroup\$ – Command Master Apr 16 at 8:51
  • 1
    \$\begingroup\$ @CommandMaster that is either the "Fetching the desired output from an external source" or the "Outsourcing the real answer" loophole. \$\endgroup\$ – the default. Apr 16 at 10:30
0
\$\begingroup\$

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.

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

Ariadne's String

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)
| |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Bubbler Apr 22 at 2:05
0
\$\begingroup\$

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:

img

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?

| |
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – null Apr 23 at 0:49
  • \$\begingroup\$ 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" \$\endgroup\$ – math junkie Apr 23 at 0:49
  • 1
    \$\begingroup\$ @HighlyRadioactive That is correct \$\endgroup\$ – golf69 Apr 23 at 0:50
  • \$\begingroup\$ Who cast the downvote? \$\endgroup\$ – null Apr 23 at 0:50
  • \$\begingroup\$ @mathjunkie I think that was already done here, and besides, ideally they would actually calculate the value instead of simply printing it \$\endgroup\$ – golf69 Apr 23 at 0:52
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Apr 23 at 2:27
  • 1
    \$\begingroup\$ Wait, I found the duplicate: Approximate the Dottie number \$\endgroup\$ – xnor Apr 23 at 2:32
0
\$\begingroup\$

Boolean Variable Satisfiability

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.

Sandbox Comments

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.

| |
\$\endgroup\$
  • \$\begingroup\$ Thanks you for using the sandbox. \$\endgroup\$ – Adám Apr 23 at 12:00
  • 1
    \$\begingroup\$ One thing that bothers me here is the combination of two tasks: a) parsing the RPN b) finding if the expression is satisfiabiable. \$\endgroup\$ – Adám Apr 23 at 12:13
  • \$\begingroup\$ 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. \$\endgroup\$ – Bubbler Apr 24 at 0:08
0
\$\begingroup\$

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.
| |
\$\endgroup\$
  • \$\begingroup\$ What would the scoring mechanism be? Code Golf? \$\endgroup\$ – math junkie Apr 23 at 16:03
  • \$\begingroup\$ @mathjunkie Damn, I forgot to specify! Code-golf, obviously. \$\endgroup\$ – null Apr 23 at 16:04
  • \$\begingroup\$ 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?). \$\endgroup\$ – Bubbler Apr 23 at 23:47
  • \$\begingroup\$ 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. \$\endgroup\$ – Bubbler Apr 23 at 23:52
0
\$\begingroup\$

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.

enter image description here

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.

enter image description here

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

| |
\$\endgroup\$
  • \$\begingroup\$ What does "the largest test case" mean? Does this task really have no pathological and trivial cases? \$\endgroup\$ – the default. Apr 21 at 14:33
  • \$\begingroup\$ @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? \$\endgroup\$ – user9207 Apr 21 at 14:59
  • \$\begingroup\$ 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". \$\endgroup\$ – the default. Apr 21 at 15:01
  • \$\begingroup\$ @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 \$\endgroup\$ – user9207 Apr 21 at 15:03
  • \$\begingroup\$ (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) \$\endgroup\$ – the default. Apr 21 at 15:07
  • \$\begingroup\$ 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. \$\endgroup\$ – Bubbler Apr 21 at 23:50
  • \$\begingroup\$ @Bubbler Thank you for reading it! I have updated the question. Please let me know if there are any other problems. \$\endgroup\$ – user9207 Apr 22 at 8:44
  • \$\begingroup\$ 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. \$\endgroup\$ – Bubbler Apr 23 at 2:22
  • \$\begingroup\$ @Bubbler Hopefully all fixed now. \$\endgroup\$ – user9207 Apr 23 at 10:51
0
\$\begingroup\$

Improved image sampling

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!

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

Fetch me some data

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

Task

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.

Input

Your code takes no input.

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?

| |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – S.S. Anne Apr 29 at 19:16
  • \$\begingroup\$ "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. \$\endgroup\$ – S.S. Anne Apr 29 at 19:17
  • \$\begingroup\$ 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? \$\endgroup\$ – the default. Apr 30 at 0:41
0
\$\begingroup\$

Is this a valid APL train?

Context

In APL, trains are tacit sequences of monadic/dyadic functions that can be called with one or two arguments. We'll code something to check if a given train follows the correct structure we need in order to have a sound train.

Task

Given the sequence of function arities in the train, determine if the train is valid as a monad and/or as a dyad. Don't forget that APL reads from right to left, so when I mention the "start" I mean the end of the array! A train is valid as a monad if

  • the train is a single monadic function; e.g. M is a valid train;
  • the train starts with a monadic function and then alternates dyadic functions with monadic functions and ends in one or two consecutive monads; e.g. MDM, MMDM and MDMDM are valid monadic trains.

A dyadic train is valid if

  • the train starts with an odd number of dyadic functions, possibly ending with a monadic function; e.g. D, MDDD and DDDDD are valid dyadic trains.

Input

Your input is going to be a list of the arities of the functions in the train, where said list contains up to 3 different elements; one for purely monadic functions, another for purely dyadic functions and another for functions that can be either monadic or dyadic, depending on usage.

The input list can be taken in any sensible format and likewise the elements can be whatever 3 distinct elements you choose. E.g. take a string with the letters MDB or take a list of integers 0,1,2. I don't mind you play around with this, just let us know what your answer uses.

APL reads from right to left and we will embody this in the challenge; input cannot be reversed.

Output

Your function should adhere to one of the two output formats:

  • output one of 3 distinct values; one for a train that only works monadically, one for a train that works dyadically and one for a train that works both ways; in this case, any consistent 3 distinct values will do;

  • output two Truthy/Falsy values, with respect to the standard Truthy/Falsy defaults of your language, where the first value flags if the train works monadically and the second to flag if the train works dyadically, or vice-versa.

Preliminary sandbox for APLers

Did I get the train rules right?

| |
\$\endgroup\$
  • \$\begingroup\$ Is it a valid APpLe train? \$\endgroup\$ – user92069 May 1 at 1:32
  • \$\begingroup\$ Related. \$\endgroup\$ – Adám May 1 at 8:12
  • \$\begingroup\$ Some test cases, please. \$\endgroup\$ – Adám May 1 at 8:20
  • \$\begingroup\$ @Adám I am waiting to confirm the rules I wrote about how trains work are correct; after that I will add the test cases! \$\endgroup\$ – RGS May 1 at 8:22
  • \$\begingroup\$ Rules look correct, but isn't there a 4th return value? What does MMM give? \$\endgroup\$ – Adám May 1 at 8:22
  • \$\begingroup\$ Are we allowed to take the input using ⊢⍀ for M and {⍺⍵} for D and for B? \$\endgroup\$ – Adám May 1 at 8:35
  • \$\begingroup\$ In fact, you can add a corresponding function valence: N; a niladic function (i.e. it can never be applied, but is nevertheless a valid function value). \$\endgroup\$ – Adám May 1 at 9:02
  • \$\begingroup\$ I think the title is wrong. Any sequence of functions form a valid train. The question is How can this train be applied? I.e. monadically, dyadically, both, or maybe not at all. \$\endgroup\$ – Adám May 1 at 9:03
0
\$\begingroup\$

Posted

| |
\$\endgroup\$
  • \$\begingroup\$ Can we require inputs to be padded for us? \$\endgroup\$ – user92069 Apr 17 at 8:14
  • \$\begingroup\$ Can we output via a digit array? \$\endgroup\$ – user92069 Apr 17 at 8:14
  • \$\begingroup\$ What do you mean by output via a digit array? Like [2,4] instead of 24? \$\endgroup\$ – Command Master Apr 17 at 8:36
  • \$\begingroup\$ 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 \$\endgroup\$ – Command Master Apr 17 at 8:38
  • 2
    \$\begingroup\$ Why base 19? That seems pretty arbitrary \$\endgroup\$ – xnor Apr 17 at 8:40
  • 1
    \$\begingroup\$ It's the smallest base for which the sum of any two digits in base 10 fit in \$\endgroup\$ – Command Master Apr 17 at 8:41
  • 1
    \$\begingroup\$ Looks like a cool challenge :) I think a few more test cases would be useful. Some slightly larger test cases would also be great \$\endgroup\$ – math junkie Apr 26 at 19:46
  • \$\begingroup\$ I doubt that there is any approach other than "take the decimal digits, sum the digits as vectors and convert from base 19" here. \$\endgroup\$ – the default. May 1 at 2:43
0
\$\begingroup\$

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!

Task:

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?
| |
\$\endgroup\$
  • \$\begingroup\$ So do we choose our own value for n, or is there some value you want us to use. \$\endgroup\$ – Lyxal May 2 at 3:00
  • \$\begingroup\$ I think this challenge is extremely similar to this one: Make your code error but only sometimes \$\endgroup\$ – math junkie May 2 at 3:20
  • \$\begingroup\$ @mathjunkie I saw that, but this question is more specific for how it should function. \$\endgroup\$ – Wezl May 2 at 18:10
  • \$\begingroup\$ @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. \$\endgroup\$ – Wezl May 2 at 18:12
  • \$\begingroup\$ is that 0-n or 1-n inclusive, exclusive, or half-open? Also, some languages give error messages when they exit with failure. \$\endgroup\$ – S.S. Anne May 2 at 18:24
  • \$\begingroup\$ @S.S.Anne I meant to say you can choose. Fixing. \$\endgroup\$ – Wezl May 2 at 18:27
  • \$\begingroup\$ 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. \$\endgroup\$ – S.S. Anne May 2 at 18:33
  • 1
    \$\begingroup\$ I suggest tagging it code-golf instead of popularity-contest because popcons are netoriously difficult to do right. \$\endgroup\$ – Lyxal May 3 at 1:14
  • 3
    \$\begingroup\$ Pseudocode of (likely) most answers you will get: 1/(rand()%n); \$\endgroup\$ – the default. May 3 at 3:33
  • \$\begingroup\$ @lyxal but maybe I should make it popularity-contest and encourage people to vote for ones that do not follow 1/(rand()%n)? \$\endgroup\$ – Wezl May 4 at 13:55
  • \$\begingroup\$ posted \$\endgroup\$ – Wezl May 4 at 15:29
0
\$\begingroup\$

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.

Your answer should be functioning revisit as per revisit version 0.1.

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

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

Compass and straightedge segment reduction

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?

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

Continue an arithmetic-geometric progression

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!

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

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!

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

Subtract a list

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]

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

Analyze the flow

Posted

| |
\$\endgroup\$
  • \$\begingroup\$ 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" \$\endgroup\$ – math junkie May 11 at 21:27
  • \$\begingroup\$ 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? \$\endgroup\$ – Domenico Modica May 12 at 0:36
  • \$\begingroup\$ @math junkie anyway thanks for the grammar corrections, also in the main post :D \$\endgroup\$ – Domenico Modica May 13 at 19:42
0
\$\begingroup\$

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
  • It's enough if you can only ask an expression about who they are. If you ask them "what will A answer if I ask B" the answer is just "(A is liar) xor B". "Did A tell lie when answering B" is just "(A's answer) xor B". Questions about the current ask or future ask may lead to paradox and are not allowed.
  • 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.
| |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Redwolf Programs May 14 at 21:23
  • 1
    \$\begingroup\$ @RedwolfPrograms Yes a,b,c are given, and possibly zero. Link don't match this problem well \$\endgroup\$ – l4m2 May 15 at 2:48
  • \$\begingroup\$ Wouldn't it require at least 4 questions for the test case (1, 1, 1)? How to solve in 3? \$\endgroup\$ – user202729 May 16 at 3:46
  • \$\begingroup\$ @user202729 brainden.com/forum/topic/… (not wiki answer as it assume answer from random is either true or false) \$\endgroup\$ – l4m2 May 16 at 3:47
  • \$\begingroup\$ Oh wiki also has a standard solution \$\endgroup\$ – l4m2 May 16 at 3:53
  • 1
    \$\begingroup\$ @RedwolfPrograms Formal description (according to my understanding of the statement) \$\endgroup\$ – user202729 May 16 at 4:48
0
\$\begingroup\$

Coronavirus Spread

Any improvements/advice is most welcome, just comment!


Because the coronavirus is still at large, I thought it would be fitting to have a epidemic-themed challenge.

Challenge

You are given a 2D array of people, where 1 represents someone with the virus, and 0 represents someone without the virus. Every day, the people with the virus infect their neighbours. You must calculate, given such a grid, how many days it will take to infect the population (i.e., every item is 1).

Rules

  • The input counts as Day 0, and every day after increases by 1
  • The grid items don't have to be 1s and 0s, they can be any similar values (e.g., true and false). Every item in the grid is randomized (50/50) to one of those values.
  • The grid can be any size between 2x2 and 100x100. The grid does not have to be square. The grid size is randomized.
  • Diagonal squares do not count as adjacent
  • This is , so the shortest answer wins!

Examples

[[1, 0, 0, 0, 1],  # Input
 [0, 1, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 1, 0]]

[[1, 1, 0, 1, 1],  # Day 1
 [1, 1, 1, 0, 1], 
 [0, 1, 0, 1, 0], 
 [0, 0, 1, 1, 1]]

[[1, 1, 1, 1, 1],  # Day 2
 [1, 1, 1, 1, 1], 
 [1, 1, 1, 1, 1], 
 [1, 1, 1, 1, 1]]

output = 2
[[1, 0],  # Input
 [0, 0],
 [0, 0]]

[[1, 1],  # Day 1
 [1, 0],
 [0, 0]]

[[1, 1],  # Day 2
 [1, 1],
 [1, 0]]

[[1, 1],  # Day 3
 [1, 1],
 [1, 1]]

output = 3

Bonus challenge: You could try to return the indices (across,down) of the people infected each day, e.g. for the example above the output could look something like:

output = {
  days: 3,
  indices: [
             [[1,2], [2,1]], 
             [[2,2], [1,3]], 
             [[2,3]]
           ]
}

| |
\$\endgroup\$
1
85 86
87
88 89
100

You must log in to answer this question.

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