539
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts 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!

\$\endgroup\$
0

3548 Answers 3548

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

Ordinal to Cardinal

Given a positive integer represented as the English spelling of an ordinal number, return the equivalent cardinal number.

Rules

  • Where an integer requires multiple words to spell, only the last word changes.

  • The following integers are strongly irregular:

    • "one" becomes "first"
    • "two" becomes "second"
    • "three" becomes "third"
  • Other integers take a suffix of "th", however there are a few integers that are weakly irregular:

    • "five" becomes "fif(th)"
    • "eight" becomes "eigh(th)"
    • "nine" becomes "nin(th)"
    • "twelve" becomes "twelf(th)"
    • "twenty" to "ninety" become "twentie(th)" to "ninetie(th)".
  • The input can be assumed to be the English spelling of an ordinal number that follows the above rules to transform it into the equivalent cardinal number.

Examples

  • "one hundred and nineteen" becomes "one hundred and nineteenth"
  • "one hundred and twenty" becomes "one hundred and twentieth"
  • "one hundred and twenty one" becomes "one hundred and twenty first"

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

\$\endgroup\$
10
  • \$\begingroup\$ There are a lot of loosely related challenges, with this one being the closest. I don't think this is a dupe at all, though, since the amount to change is much more significant. Is there an upper limit on the input? If not, you definitely need to specify how the larger numbers might appear i.e. do we need to handle "milliard" as well as "million"? \$\endgroup\$ Mar 26 '20 at 15:47
  • \$\begingroup\$ @FryAmTheEggman That and the other challenge takes the numbers as digits rather than words, which IMHO is a significant difference already. As for large numbers, you can assume for the purposes of the question that any number I forgot about takes a "th" suffix. \$\endgroup\$
    – Neil
    Mar 26 '20 at 22:30
  • \$\begingroup\$ Which integers do we need to handle? I'd suggest limiting it to, say, numbers from 1 to 99. Or if you do want all positive integers, could you please clarify how these are written out? \$\endgroup\$
    – xnor
    Mar 27 '20 at 20:57
  • \$\begingroup\$ @xnor a) this challenge is about words, not numbers b) the rules are there, I don't understand what you're missing \$\endgroup\$
    – Neil
    Mar 27 '20 at 21:51
  • \$\begingroup\$ @Neil Like, is "one billion, two hundred and thirty four million, five hundred and sixty seven thousand, eight hundred and ninety" a possible input, for which the output would be "one billion, two hundred and thirty four million, five hundred and sixty seven thousand, eight hundred and ninetieth"? If so, what is the exact format for such numbers? I understand that really only the last word matters for the conversion in the challenge, but it might make a difference for, say, a regex that does a replacement that might falsely trigger on something like "Duotrigintillion". \$\endgroup\$
    – xnor
    Mar 27 '20 at 22:01
  • \$\begingroup\$ @xnor Why would it falsely trigger on duotrigintillion? Is there no duotrigintillionth? \$\endgroup\$
    – Neil
    Mar 27 '20 at 22:39
  • \$\begingroup\$ @Neil I mean if it's part of a longer number and the regex does a replacement that doesn't check for the end of the string, but simply replaces certain sequences of characters. Duotrigintillion is an arbitrary example; I don't expect it specifically to actually "collide" with anything useful. \$\endgroup\$
    – xnor
    Mar 27 '20 at 22:42
  • \$\begingroup\$ @xnor Well, surely if it collides as the last word, then it will collide as an earlier word, which would be an error, according to the first rule? \$\endgroup\$
    – Neil
    Mar 27 '20 at 23:41
  • \$\begingroup\$ @Neil Oh, you're right, that would catch it. Maybe a more useful example is "one hundred and one" wrongly being made into 'first hundred and first". In any case, I think it would be useful to either add large-valued test cases or put an upper bound. \$\endgroup\$
    – xnor
    Mar 28 '20 at 0:54
  • \$\begingroup\$ @xnor I still don't see that it needs an upper bound. You can just assume that the rules I've given apply, even if they don't in real life for some reason. \$\endgroup\$
    – Neil
    Mar 28 '20 at 1:07
0
\$\begingroup\$

Mom-rounding the time

Context

Growing up with my mother, whenever she looked at a clock to check the time, she would always say "shoot, it's already X!" and then I would look at the clock and realize she was just rounding the time in a really weird way.

Task

Given a time with hours and minutes, round it like my mom would. Rounding always occurs upwards. Say it is currently H hours and M minutes.

  • if M is 0, no rounding occurs; my mom isn't that crazy;
  • if M is 9 or less, my mom rounds to H:15;
  • if M is 19 or less, my mom rounds to H:30;
  • if M is 34 or less, my mom rounds to H:45;
  • for any other value of M, my mom rounds to H+1:00.

Input

You will take a time that needs rounding, in any sensible format. ISO strings for date/time, two integers representing hours/numbers, a string with two integers and a separator; these are all fair game.

Output

The string "shoot, it's already X" with X replaced with the mom rounding time.

Scoring

This is so shortest answer wins. However, if your source code contains the substring shoot, it's already then you may subtract 19 from your score.

Test cases

Here is the program I use to generate the test cases.

11:00 -> shoot, it's already 11:00!
 3:08 -> shoot, it's already 03:15!
 1:09 -> shoot, it's already 01:15!
13:13 -> shoot, it's already 13:30!
 2:35 -> shoot, it's already 03:00!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ +1 because my mom's rounding is similarly weird too. One thing though: shoot, it's already has a ' which must be escaped in many languages, and the substring condition is unfairly penalizing langauges without string literal support. \$\endgroup\$
    – Bubbler
    Apr 1 '20 at 0:16
  • 5
    \$\begingroup\$ I suggest removing the unnecessary fluff about adding text and only keep the conversion. Bonuses in code golf are bad in general. Here it seems you try to even the playing field by explicitly disadvantaging languages with string compression, but end up making the false assumption that the substring will occur if used literally, even though some languages will need to escape the quote. \$\endgroup\$
    – Adám
    Apr 1 '20 at 6:17
  • 2
    \$\begingroup\$ Assuming hours wrap around in 24-hour time, some test cases showing this would be good. \$\endgroup\$
    – xnor
    Apr 1 '20 at 9:25
  • \$\begingroup\$ Those bullet-points should either be else-ifs instead of ifs or you should just define ranges. Currently a minute of 3 would first be rounded to 15 for being <=9, then 15 is rounded again to 30 for being <=19, and then again to 45 for being <=34. So basically: 0 remains 0; <=34 becomes 45, and >34 becomes 0 with the hour increasing, and the other bullet-points could be ignored. I think something like M=0→H:00; M=[1,9]→H:15; M=[10,19]→H:30; M=[20,34]→H:45; M=[35,59]→H+1:00 (perhaps in text form) would be clearer imo. \$\endgroup\$ Apr 1 '20 at 10:10
  • \$\begingroup\$ @petStorm thanks for your edit but I would prefer if you did not edit any reference programs into my sandboxed posts (you may comment with a TIO link) nor edited the challenge to cope with the feedback I get from commenters, nor to include a whole "test cases" section (but you can include it in your TIO link). In particular, usually when I don't include test cases right from the start is because I want to polish the spec a bit before trying to understand what test cases are really relevant and needed. \$\endgroup\$
    – RGS
    Apr 1 '20 at 11:50
  • 1
    \$\begingroup\$ And this is especially true because you create a whole section and then write "Here is the program I used to generate the test cases" as if you were me, which is not ok. \$\endgroup\$
    – RGS
    Apr 1 '20 at 11:52
0
\$\begingroup\$

\$\endgroup\$
6
  • \$\begingroup\$ I like this idea. Do we have a default for taking "infinite lists" as input? I'd mildly suggest limiting the numbers to positive integers on general principle. \$\endgroup\$
    – xnor
    Apr 2 '20 at 4:26
  • \$\begingroup\$ How do you propose taking an infinite list as input? I think the natural approach would use as "input" a program (or function with no arguments) that runs forever; the list would consist of the numbers that it outputs when run. (This would be sort of like a plug-in that your answer could use.) The problem is that that might make the challenge trivial. But I'm not sure how else to take the input list. \$\endgroup\$ Apr 2 '20 at 6:14
  • \$\begingroup\$ In some languages the input could be a stream or iterator \$\endgroup\$ Apr 2 '20 at 8:36
  • \$\begingroup\$ I don't know what you want to allow, but some other possible implementations of infinite lists could be as a generator function that produces a new value on each call, or a black-box function taking a natural n and giving the n'th value. \$\endgroup\$
    – xnor
    Apr 2 '20 at 12:35
  • \$\begingroup\$ @xnor I don't think I will limit it to positive integers because positive integers are not bounded below, meaning sequences could only increase. This pretty radically changes the content of the challenge. \$\endgroup\$
    – Grain Ghost Mod
    Apr 2 '20 at 13:14
  • \$\begingroup\$ Let the first and second items of the list be x and y respectively. This checks whether input-x is divisible by y-x. (Doesn't work sometimes, I'll take a look.) \$\endgroup\$
    – user92069
    Apr 3 '20 at 7:27
0
\$\begingroup\$

How many Temtem can I breed?

Temtem is a monster-catching MMORPG. Within the game you have the ability to breed two Temtem to create an egg which then hatches into the baby of its mother. The ability to do this depends on several properties of the parent Temtem:

  • A Temtem has a gender, which is either male or female. To breed, you need one Temtem of each gender.
  • A Temtem has one or two types. A pair of Temtem can only breed if they have a type in common.
  • A Temtem has a fertility which ranges from 0 to 8. Temtem with a fertitilty of 0 can no longer breed in captivity. The fertility of each parent decreases by 1 when they breed.

The resulting Temtem inherits some of its properties from its parents.

  • The baby Temtem's gender is random. For the purposes of this question, this means that you can choose the gender, but you cannot change it later.
  • The baby Temtem inherits its mother's type. (This is not strictly true but it is always possible to evolve the baby to give the mother's type if necessary.)
  • The baby Temtem inherits the lesser of its parents' fertility.

Simple example:

  • One female Temtem with fertility 3 and one male Temtem with fertility 2 of the same type.
  • Breeding reduces their fertility to 2 and 1 and we choose the baby, which also has 1 fertility, to be male.
  • The female can breed again with both males, at which point all the Temtem now have 0 fertility.
  • This gives you a total of five Temtem.

You challenge is to write a program or function which accepts a list of Temtem and outputs the maximum number of Temtem it is possible to breed, assuming luck is on your side.

You can use any convenient input method for the Temtem, as long as it breaks no standard loopholes. For instance, you could use a string of three or four characters encoding the gender, fertility and type(s). (Your input method must be able to support 12 different types and 132 different pairs of types.)

You can output either the total number or the number of new Temtem, or you can also output the resulting list of Temtem in the order they were born.

This is , so the shortest program or function wins!

\$\endgroup\$
1
  • \$\begingroup\$ Without the types this makes an interesting "limited Fibonacci-like" growth - I'd be curious to see if it had already been studied. I think adding in the types makes it more likely that brute forcing will be the best approach. I haven't done much work on this yet, so of course I could be wrong. Separately, this definitely needs a test case where inter-type breeding gives a larger result than handling each separately, though I'm pretty sure you knew that. \$\endgroup\$ Apr 6 '20 at 16:47
0
\$\begingroup\$

Word Grid Puzzle Iterator

I commonly see an advert for a word-based game, where, by removing a word from a grid of letters, the remaining letters "collapse", horizontally and vertically, leading to further words being findable.

The challenge is to take in a grid of characters and a word as an input, and output the collapsed grid after that word has been removed.

Words in the grid could be oriented in any direction.

This is code-golf, usual exclusions apply.

Example

The following set of examples follow on from each other - so the output from the first example is the input to the second.

AIR

In:

N   F   A   D   S   T
I   O   I   E   N   T
A   G   R   W   O   H
R   L   I   A   H   A
S   L   E   E   W   W

Out: If the word "AIR" is removed, none of the rows or columns are empty and so the rest of the grid remains as-is:

N   F       D   S   T
I   O       E   N   T
A   G       W   O   H
R   L   I   A   H   A
S   L   E   E   W   W

HAIL

If the word "HAIL" is removed, the letters in the 2nd-5th columns drop down one, making the word "SNOW" accessible:

N                   T
I   F       D   S   T
A   O       E   N   H
R   G       W   O   A
S   L   E   E   W   W

SNOW

If SNOW is removed, the columns collapse horizontally:

N               T   
I   F       D   T   
A   O       E   H   
R   G       W   A   
S   L   E   E   W   

THAW

If THAW is removed, the T drops down so that SLEET is now accessible:

N                       
I   F       D       
A   O       E       
R   G       W       
S   L   E   E   T   

SLEET

Removing SLEET clears a row and a column, and so the grid collapses in both directions:

                    
N                   
I   F   D           
A   O   E           
R   G   W           

RAIN, DEW, FOG

The remaining three vertical words (RAIN, DEW, FOG) can then be removed individually:

                    
                    
F   D               
O   E               
G   W               
                    
                    
F                   
O                   
G                   
                    
                    
                    
                    
                    

Notes

In the above examples, I have not resized the arrays as the outside rows/columns are made empty; instead just leaving them blank (i.e. the final array is 6x5, as is the starting array). Your program may also do this, or it may resize the array to remove empty rows and columns if you prefer.

For example, assuming the input is a 1x5 array:

H A T C E removing HAT could become _ _ _ C E or CE, both are valid. (underscores represent spaces for formatting purposes)

Inputs and Outputs:

Any reasonable format is acceptable - arrays, strings, etc. But:

  • you cannot assume that the orientation of the word to remove is the same as that in the input. e.g you won't get the input "LIAH" because the word HAIL is written right-to-left on the grid.
  • the output must be the same format as the input (i.e. the program must accept the output from the previous iteration as the grid input to the next)
  • You can assume the word will be in the grid, horizontally or vertically (not diagonally)
  • Words will never contain spaces, only the letters A-Z; and if the word is found but with a space in it, then that doesn't count as matching the word
    • You can assume the case of the word will match the grid, in whatever case suits your language (UPPER, lower, camelCase, whatever)
  • You can assume that the Input word will only appear once on the grid

Sandbox Questions

  • Does this feel too much like multiple challenges (find the word, collapse the array)?
\$\endgroup\$
3
  • \$\begingroup\$ I think the idea stands on its own logically, though perhaps there is a dupe out there somewhere. Separately, I think you should explain the situation where a word appears more than once. Your resizing comment also seems a bit odd: I would expect that if instead of HAIL the input was AGWOH the word wouldn't be able to be removed. \$\endgroup\$ Apr 3 '20 at 20:20
  • \$\begingroup\$ Thanks for your comments as always. I have tried to clarify. I'm not sure what you mean about the resizing comment - only empty rows and columns can be removed; and words will always be A-Z (or whatever case you prefer) and must match exactly the input, in any orientation. \$\endgroup\$ Apr 6 '20 at 7:43
  • \$\begingroup\$ I see, that is what I expected, but when I read the challenge I was unsure. I think your edit makes it much clearer. (What I was trying to get at was that I expected gaps in unempty rows/columns to be "unmatchable", which I think before was made somewhat ambiguous by the wording of the purely aesthetic output) \$\endgroup\$ Apr 6 '20 at 16:30
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\$
3
  • 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 '20 at 1:43
  • \$\begingroup\$ @Bubbler Thx. I tried to be clearer about randomness expectations. \$\endgroup\$
    – david
    Apr 11 '20 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 '20 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\$
3
  • \$\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\$ Apr 12 '20 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 '20 at 9:25
  • \$\begingroup\$ Maybe you can add more test-cases \$\endgroup\$ Apr 12 '20 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\$
5
  • \$\begingroup\$ I fail to see how this is a bracket. \$\endgroup\$ Apr 13 '20 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\$ Apr 13 '20 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\$
    – Grain Ghost Mod
    Apr 13 '20 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\$
    – Grain Ghost Mod
    Apr 13 '20 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 '20 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\$
11
  • 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\$ Apr 12 '20 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 '20 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\$ Apr 12 '20 at 15:37
  • \$\begingroup\$ Done. Thanks! @FryAmTheEggman \$\endgroup\$
    – newbie
    Apr 12 '20 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\$ Apr 13 '20 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 '20 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\$ Apr 13 '20 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 '20 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 '20 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 '20 at 1:29
  • \$\begingroup\$ Alright, I would go with output \$d\$. \$\endgroup\$
    – newbie
    Apr 14 '20 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\$
1
  • \$\begingroup\$ What's the scoring mechanism? Code Golf I assume? \$\endgroup\$ Apr 24 '20 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\$
2
  • \$\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\$ Apr 16 '20 at 10:31
  • \$\begingroup\$ I'm not sure, but from what I've seen it seems like it \$\endgroup\$ Apr 16 '20 at 12:33
0
\$\begingroup\$

This Question Has _____ Views

posted

\$\endgroup\$
4
  • \$\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\$ Apr 16 '20 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 '20 at 8:48
  • 1
    \$\begingroup\$ someone can register a domain which will retrive the live number \$\endgroup\$ Apr 16 '20 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\$ Apr 16 '20 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\$
1
  • \$\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 '20 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\$
7
  • \$\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 '20 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\$ Apr 23 '20 at 0:49
  • 1
    \$\begingroup\$ @HighlyRadioactive That is correct \$\endgroup\$
    – golf69
    Apr 23 '20 at 0:50
  • \$\begingroup\$ Who cast the downvote? \$\endgroup\$
    – null
    Apr 23 '20 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 '20 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 '20 at 2:27
  • 1
    \$\begingroup\$ Wait, I found the duplicate: Approximate the Dottie number \$\endgroup\$
    – xnor
    Apr 23 '20 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\$
3
  • \$\begingroup\$ Thanks you for using the sandbox. \$\endgroup\$
    – Adám
    Apr 23 '20 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 '20 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 '20 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\$
4
  • \$\begingroup\$ What would the scoring mechanism be? Code Golf? \$\endgroup\$ Apr 23 '20 at 16:03
  • \$\begingroup\$ @mathjunkie Damn, I forgot to specify! Code-golf, obviously. \$\endgroup\$
    – null
    Apr 23 '20 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 '20 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 '20 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\$
9
  • \$\begingroup\$ What does "the largest test case" mean? Does this task really have no pathological and trivial cases? \$\endgroup\$ Apr 21 '20 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 '20 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\$ Apr 21 '20 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 '20 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\$ Apr 21 '20 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 '20 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 '20 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 '20 at 2:22
  • \$\begingroup\$ @Bubbler Hopefully all fixed now. \$\endgroup\$
    – user9207
    Apr 23 '20 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\$
3
  • \$\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 '20 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 '20 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\$ Apr 30 '20 at 0:41
0
\$\begingroup\$

Posted

\$\endgroup\$
8
  • \$\begingroup\$ Can we require inputs to be padded for us? \$\endgroup\$
    – user92069
    Apr 17 '20 at 8:14
  • \$\begingroup\$ Can we output via a digit array? \$\endgroup\$
    – user92069
    Apr 17 '20 at 8:14
  • \$\begingroup\$ What do you mean by output via a digit array? Like [2,4] instead of 24? \$\endgroup\$ Apr 17 '20 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\$ Apr 17 '20 at 8:38
  • 2
    \$\begingroup\$ Why base 19? That seems pretty arbitrary \$\endgroup\$
    – xnor
    Apr 17 '20 at 8:40
  • 1
    \$\begingroup\$ It's the smallest base for which the sum of any two digits in base 10 fit in \$\endgroup\$ Apr 17 '20 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\$ Apr 26 '20 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\$ May 1 '20 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\$
11
  • \$\begingroup\$ So do we choose our own value for n, or is there some value you want us to use. \$\endgroup\$
    – lyxal
    May 2 '20 at 3:00
  • \$\begingroup\$ I think this challenge is extremely similar to this one: Make your code error but only sometimes \$\endgroup\$ May 2 '20 at 3:20
  • \$\begingroup\$ @mathjunkie I saw that, but this question is more specific for how it should function. \$\endgroup\$ May 2 '20 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\$ May 2 '20 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 '20 at 18:24
  • \$\begingroup\$ @S.S.Anne I meant to say you can choose. Fixing. \$\endgroup\$ May 2 '20 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 '20 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 '20 at 1:14
  • 3
    \$\begingroup\$ Pseudocode of (likely) most answers you will get: 1/(rand()%n); \$\endgroup\$ May 3 '20 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\$ May 4 '20 at 13:55
  • \$\begingroup\$ posted \$\endgroup\$ May 4 '20 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\$
1
96 97
98
99 100
119

You must log in to answer this question.

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