490
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| |
\$\endgroup\$

2955 Answers 2955

1
46 47
48
49 50
99
1
\$\begingroup\$

Recolour my Table (WIP)

I have an oak table. It's a very nice oak table. But recently, I've noticed that my table has been getting some sort of white patches on it:

Insert picture of my table here.

Now, I like my table, and I don't want my table getting all dirty. I'm asking y'all to fix this for me, so that my table will once again be clean.

The Challenge

Given a picture of the table in question, replace all pixels that are white with the correct table colour. I know I'll need to specify this area better, but I don't know how to. Suggestions are welcome.

Rules

Unsure

Scoring

This is , so the answer with the fewest amount of bytes wins.

| |
\$\endgroup\$
  • \$\begingroup\$ Maybe try limiting the table format. Is it top down or sideways? Also can we assume that the original table color (or slight variation to a certain HSL difference, maybe) is the majority of the image? \$\endgroup\$ – Roman Gräf Feb 6 at 19:50
1
\$\begingroup\$

floating-point error matters

Write a expression of floating-point numbers in any languages. When calculating the expression without floating-point errors (as what a human do), it should be 0. But with floating-point errors (as what happened in your language), it yield 1 instead.

  • Floating-point numbers are some numbers which store a finite number digits (binary or decimal or in any other bases) of fraction, plus an exponent in computer. It may be IEEE 754, but not must be.
  • Loss of precision due to integer types (which do not has a exponent) are not allowed in the expression. You are still allowed to include integers (or even other types) in your expression as long as operations such as rounding into an integer are not the root of errors.

Shortest codes win as code-golf.


Sandbox:

  • Is there any duplicates here?
  • Is asking for an expression instead of full program allowed?
| |
\$\endgroup\$
  • \$\begingroup\$ Yes, you can allow expressions. Good fit for this one, imho. \$\endgroup\$ – Adám Feb 6 at 11:33
1
\$\begingroup\$

No title yet.

By Zekendorf's theorem every non-negative integer has a unique representation as the sum of Fibonacci numbers where no two numbers coincide or are adjacent.

In The minimum fibonacci challenge! the challenge was to output the list of Fibonacci numbers. However, you can instead consider the list of coefficients of the sum \$ \small x_0F(2) + x_1F(3) + x_2F(4) + \ldots \$ (since \$ \small F(0) = 0 \$ and \$ \small F(1) = F(2) \$ never appear in the Zekendorf representation) and represent that as a binary number \$ \ldots x_2 x_1 x_0 \$, e.g. \$ \small 67 = \small 1F(2) + 0F(3) + 1F(4) + 0F(5) + 1F(6) + 0F(7) + 0F(8) + 0F(9) + 1F(10) \$ which we can represent using the binary number \$ \small 100010101 \$ or \$ \small 277 \$ in decimal.

We can readily convert the binary representation back into the original integer by calculating the sum of the relevant Fibonacci numbers. However, I would like you to, given an input integer \$ \small n \$, output the decimal integer whose binary representation encodes the Zekendorf representation of \$ \small n \$ in this way.

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

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I would clarify that your binary representation is "flipped", i.e. 0-extends infinitely to the left. \$\endgroup\$ – Jonathan Frech Feb 8 at 18:32
  • \$\begingroup\$ @JonathanFrech flipped in comparison to what? \$\endgroup\$ – RGS Feb 10 at 20:18
  • \$\begingroup\$ @RGS I wrote the Fibonacci coefficients from left to right but the bits in the binary number from right to left and it wasn't so clear before. \$\endgroup\$ – Neil Feb 10 at 21:15
  • \$\begingroup\$ Oh ok, but that still matches what we don in binary. I can also write 11 = 1 + 2 + 8 and \$11 = 1011_2\$ :) but sure, going for perfect clarity is better than trusting other people's common sense \$\endgroup\$ – RGS Feb 10 at 21:54
  • 2
    \$\begingroup\$ @RGS Having to guess the specifications from a single example is not really common sense as it is annoying. \$\endgroup\$ – Jonathan Frech Feb 11 at 21:41
1
\$\begingroup\$

Calculate Mahjong points

Introduction to Mahjong tiles

Mahjong (麻雀) is a board game that originates from China. Mahjong tiles used in this challenge are in Unicode points U+1F000 – U+1F021:

🀀🀁🀂🀃🀄🀅🀆🀇🀈🀉🀊🀋🀌🀍🀎🀏🀐🀑🀒🀓🀔🀕🀖🀗🀘🀙🀚🀛🀜🀝🀞🀟🀠🀡

They are categorized as:

  • Winds (風牌): 🀀(East Wind), 🀁(South Wind), 🀂(West Wind), 🀃(North Wind)

  • Dragons (三元牌): 🀄(Red Dragon), 🀅(Green Dragon), 🀆(White Dragon)

  • Ten Thousands (萬子): 🀇(One of the Ten Thousands) through 🀏(Nine of the Ten Thousands)

  • Bamboos (索子): 🀐(One of the Bamboos; note that it depicts a bird) through 🀘(Nine of the Bamboos)

  • Circles (筒子): 🀙(One of the Circles) through 🀡(Nine of the Circles)

  • Winds and Dragons are together called Honors (字牌).

  • Ten Thousands, Bamboos and Circles are each called a suit and together called Numbers (数牌). They have ranks from 1 to 9.

  • Among Numbers, the Ones and the Nines are called Terminals (老頭牌). The Twos through the Eights are called Simples (中張牌).

  • Honors and Terminals are together called Orphans (幺九牌).

Every Mahjong tiles have 4 copies of themselves.

Mahjong Hand

A legal Hand will be given as the input. It consists of:

  • A Head, which is 2 identical tiles.

  • 4 Bodies, each which is either:

    • A Sequence, which is 3 consecutive Numbers of the same suit.

    • A Triplet, which is 3 identical tiles.

Hence, a Hand consists of 14 tiles.

There are exceptions. See "Seven Heads" and "Thirteen Orphans" below.

Points

The objective is to calculate how many points a Hand has. Points are gained by having Yakus (役), which are cumulative.

Also I apologize that I named these Yakus to be more intuitive for the code golf, making them differ from the 'usual' names. Sorry!

1 Point Yakus

  • Menzen Tsumo (門前清自摸和), which is worth 1 point, will always be assumed.

  • Pinfu (平和): Get a non-Dragon Head and 4 Sequences.

    • Example: 🀃🀃🀇🀈🀉🀑🀒🀓🀔🀕🀖🀟🀠🀡
  • One Pair (一盃口): Get 2 identical Bodies.

    • Example: 🀂🀂🀂🀇🀇🀇🀈🀉🀓🀓🀔🀔🀕🀕
  • Dragon Triplet (役牌): Get a Triplet of Dragons. Multiple Dragon Triplets are cumulative.

    • Example: 🀆🀆🀆🀇🀈🀉🀊🀊🀒🀓🀔🀛🀜🀝
  • All Simples (断幺九): Let the Hand consist only of Simples.

    • Example: 🀈🀉🀊🀓🀓🀓🀚🀛🀛🀜🀜🀝🀠🀠

2 Points Yakus

  • Seven Heads (七対子): Get 7 Heads. It cannot contain 2 identical Heads.

    • Example: 🀀🀀🀂🀂🀆🀆🀈🀈🀊🀊🀐🀐🀛🀛
  • Colorful Sequences (三色同順): Get a sequence for each suit, consisting of the same set of ranks.

    • Example: 🀀🀀🀁🀁🀁🀉🀊🀋🀒🀓🀔🀛🀜🀝
  • Full Sequence (一気通貫): Get 3 sequences of the same suit, consisting of ranks of 123, 456, and 789.

    • Example: 🀀🀀🀁🀁🀁🀇🀈🀉🀊🀋🀌🀍🀎🀏
  • Semi-Orphans (チャンタ): Let all Heads and Bodies have at least 1 Orphan.

    • Example: 🀀🀀🀁🀁🀁🀇🀈🀉🀐🀑🀒🀡🀡🀡
  • Concealed Three (三暗刻): Get 3 Triplets.

    • Example: 🀀🀀🀁🀁🀁🀊🀊🀊🀋🀋🀋🀑🀒🀓
  • Colorful Triplets (三色同刻): Get a Triplet for each suit, consisting of the same rank.

    • Example: 🀀🀀🀉🀊🀊🀊🀊🀋🀓🀓🀓🀜🀜🀜
  • Dragons Minor (小三元): Let the Head and 2 Bodies consist of Dragons. Cumulative with the 2 Dragon Triplets.

    • Example: 🀄🀄🀅🀅🀅🀆🀆🀆🀊🀋🀌🀒🀓🀔
  • All Orphans (混老頭): Let the Hand consist only of Orphans. Supersedes Semi-Orphans. Cumulative with Seven Heads.

    • Example: 🀁🀁🀂🀂🀃🀃🀆🀆🀇🀇🀏🀏🀘🀘
  • Three of a Kind (一色三順): Get 3 identical Bodies. Supersedes One Pair.

    • Example: 🀅🀅🀇🀇🀇🀈🀈🀈🀉🀉🀉🀙🀚🀛 (Note that this example also presents Semi-Orphans, which makes it supersede Concealed Three.)

3 Points Yakus

  • Two Pairs (兩盃口): Get 2 pairs of identical Bodies. Supersedes One Pair and Seven Heads.

    • Example: 🀃🀃🀇🀇🀈🀈🀉🀉🀑🀑🀒🀒🀓🀓
  • Semi-Terminals (純チャンタ): Let all Heads and Bodies have at least 1 Terminal. Supersedes Semi-Orphans.

    • Example: 🀇🀇🀇🀈🀉🀍🀎🀏🀏🀏🀏🀙🀙🀙
  • Semi-Flush (混一色): Let the Numbers consist of a single suit.

    • Example: 🀂🀂🀇🀈🀉🀉🀉🀉🀊🀋🀌🀌🀍🀎

6 Points Yaku

  • Flush (清一色): Let the Hand consist of a single suit of Numbers. Supersudes Semi-Flush.

    • Example: 🀇🀇🀇🀈🀉🀉🀉🀉🀊🀋🀌🀌🀍🀎

Yakumans

Yakumans (役満) worth 13 points, and supersede all Yakus above. Multiple Yakumans are cumulative.

Without Yakumans, the points are capped at 13.

  • Concealed Four (四暗刻): Get 4 Triplets.

    • Example: 🀀🀀🀉🀉🀉🀌🀌🀌🀒🀒🀒🀞🀞🀞
  • Thirteen Orphans (国士無双): Collect all 13 Orphans, plus an additional Orphan.

    • Example: 🀀🀁🀂🀃🀄🀅🀆🀇🀇🀏🀐🀘🀙🀡
  • Nine Gates (九蓮宝燈): Get Flush of ranks of 1112345678999, plus an additional Number of the same suit.

    • Example: 🀇🀇🀇🀈🀉🀊🀋🀋🀌🀍🀎🀏🀏🀏
  • All Greens (緑一色): Let the Hand consist only of Green Dragons and the Twos, Threes, Fours, Sixes, and Eights of the Bamboos.

    • Example: 🀅🀅🀅🀑🀑🀒🀒🀓🀓🀕🀕🀕🀗🀗
  • All Honors (字一色): Let the Hand consist only of Honors. Cumulative with Concealed Four.

    • Example: 🀀🀀🀀🀁🀁🀂🀂🀂🀅🀅🀅🀆🀆🀆
  • All Terminals (清老頭): Let the Hand consist only of Terminals. Cumulative with Concealed Four.

    • Example: 🀇🀇🀇🀏🀏🀏🀐🀐🀐🀘🀘🀙🀙🀙
  • Dragons Major (大三元): Get a Triplet for each of Dragons.

    • Example: 🀄🀄🀄🀅🀅🀅🀆🀆🀆🀇🀈🀉🀑🀑
  • Winds Minor (小四喜): Let the Head and 3 Bodies consist of Winds.

    • Example: 🀀🀀🀁🀁🀁🀂🀂🀂🀃🀃🀃🀖🀗🀘
  • Straight Flush (連七対): Get Seven Heads with Numbers with consecutive ranks of the same suit.

    • Example: 🀚🀚🀛🀛🀜🀜🀝🀝🀞🀞🀟🀟🀠🀠
  • Four of a Kind (一色四順): Get 4 identical Bodies.

    • Example: 🀃🀃🀓🀓🀓🀓🀔🀔🀔🀔🀕🀕🀕🀕
  • Winds Major (大四喜): Worths 2 Yakumans. Get a Triplet for each of Winds. Cumulative with Concealed Four.

    • Example: 🀀🀀🀀🀁🀁🀁🀂🀂🀂🀃🀃🀃🀖🀖
  • The Septentrions (大七星): Worths 2 Yakumans. Get a Head with each of Honors. Supersedes All Honors.

    • The only example: 🀀🀀🀁🀁🀂🀂🀃🀃🀄🀄🀅🀅🀆🀆

Other rules about Mahjong

When a Hand can be interpreted as different combinations of Heads and Bodies, the combination with the most points will be chosen. (See Three of a Kind and Two Pairs above)

Examples

🀅🀅🀋🀋🀌🀌🀍🀍🀑🀒🀓🀟🀠🀡 : Menzen Tsumo + One Pair = 2 points.

🀉🀊🀋🀌🀍🀎🀑🀒🀓🀔🀔🀞🀟🀠 : Menzen Tsumo + Pinfu + All Simples = 3 points.

🀀🀀🀀🀁🀁🀁🀂🀂🀂🀃🀃🀃🀆🀆 : Winds Major + Concealed Four + All Honors = 52 points. (Most points possible)

Rules about code golf

  • Input type and format doesn't matter, but it must consist of the Unicode characters above. In C++, valid examples include std::u8string (sorted or not) and std::multiset<u32char_t>.

  • Output type and format doesn't matter either.

  • Invalid Hands (not exactly 14 tiles, contains 5 copies of the same tile, etc) fall into don't care situation.

  • If and only if your language doesn't support Unicode, use the following table to parse Mahjong tiles:

           |x0|x1|x2|x3|x4|x5|x6|x7|x8|x9|xA|xB|xC|xD|xE|xF  
    -------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    U+1F00x|We|Ws|Ww|Wn|Dr|Dg|Dw|T1|T2|T3|T4|T5|T6|T7|T8|T9
    -------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    U+1F01x|B1|B2|B3|B4|B5|B6|B7|B8|B9|C1|C2|C3|C4|C5|C6|C7
    -------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
    U+1F02x|C8|C9|
    
| |
\$\endgroup\$
  • \$\begingroup\$ A related, more golfable challenge posted here: codegolf.stackexchange.com/q/199202/89459 \$\endgroup\$ – Dannyu NDos Feb 10 at 6:30
  • \$\begingroup\$ Maybe you need more testcase. At least one per yaku. \$\endgroup\$ – tsh Feb 10 at 14:40
  • \$\begingroup\$ Should output for 11112233778899m be 13 or 14? \$\endgroup\$ – tsh Feb 16 at 7:02
  • \$\begingroup\$ @tsh Since it has no Yakuman, its point is capped at 13. \$\endgroup\$ – Dannyu NDos Feb 16 at 7:06
  • \$\begingroup\$ Is Straight Flush (連七対) required to be All Simples (断幺九)? \$\endgroup\$ – tsh Feb 16 at 7:15
  • \$\begingroup\$ @tsh No. 小車輪, 大車輪, and their correspondent to other suits are all Straight Flush. \$\endgroup\$ – Dannyu NDos Feb 16 at 7:17
1
\$\begingroup\$

Be second to last

This is a challenge with a game with a clear winning strategy, but the winner is not the one who comes in first, but the one who comes in second to last! While losing is easy (just throw every game), just barely not losing is quite a task.

The Game

The bots will be made to play games of normal Nim against each other. The rules are as follows:

  • The board consists of a list of unsigned integers
  • In alternating turns, the players reduce one non-zero element by an amount of their choosing, as long as the element is not negative afterwards
  • The player who reduces the list to all entries being 0 wins

The length of the Nim list and its entries will be randomly determined for each game.

The Tournament

All bots will compete against each other in a Danish-Style tournament:

  • Initially, players are assigned positions in a list randomly
  • After each round, the list is sorted by the amount of wins with an order-preserving method
  • In each round, the players with the odd numbers play against those with the following even numbers (so 1st against 2nd, 3rd against 4th, and so forth)
  • If the number of players is odd, the one in the middle position has a bye and is given 1 win without playing.
  • The tournament ends after \$\lceil \log_{2}(N_{Players}) \rceil\$ (Binary logarithm of the number of players, rounded up) rounds.

The player in the second to last position of the list counts as the total winner of the tournament.

King of the Hill

Each time the contest is run, 100 tournaments are played. The bots with the highest number of being second to last is the overall winner.

Challenge Rules

  • Each bot is a Python 3 class implementing the following functions:
    • __init__(ID, n) passes the bot its randomly assigned ID for this tournament, and the total number of players.
    • nim(self,list) which takes in the Nim board state and returns a tuple (index, amount), specifying from which list index to subtract what number. This function is repeatedly called during each game of Nim played, until a winner has been determined.
    • rank(self,IDs,scores) which takes in the current order of ranking in the tournament, and the list of scores of each bot, ordered by ID. It returns nothing. This will be called for each bot after each round of tournament, as well as before the first round, to provide the ranking information if the bot requires it.
  • Bots are explicitly allowed to implement further functions and store data for private use. Bots will only be deleted and re-initialized after each full tournament.
  • Programming meta-effects are forbidden, meaning any attempts to directly access other bots' code, the Controller's code, causing Exceptions or similar. Any bot doing so is disqualified until fixed.
  • The following will also be set up to cause Exceptions:
    • nim returning an index of which the element is already 0
    • nim return an amount larger than the element at that index
  • Other languages are allowed only in case they can be easily converted to Python 3.
  • Class names have to be unique
  • Multiple bots per person are allowed, but only the latest version will be taken of iteratively updated bots.
  • As per Standard Loopholes, copies of bots are not allowed. This includes bots who differ from other bots only by a trivial change in strategy (e.g. a change in the pseudorandom seed).

Controller and Examples

Watch this space.

| |
\$\endgroup\$
  • \$\begingroup\$ this sounds fun! I have no idea how it fits this community, but I can't wait to see this in the main site! \$\endgroup\$ – RGS Feb 11 at 16:04
  • \$\begingroup\$ @RGS king-of-the-hill challenges are common -- not all challenges have to be code-golf. \$\endgroup\$ – S.S. Anne Feb 11 at 23:55
  • \$\begingroup\$ @S.S.Anne I know not everything has to be code golf, I'm just saying that in the little time I've been active, I've never seen a KotH challenge \$\endgroup\$ – RGS Feb 12 at 7:01
  • \$\begingroup\$ Me neither. This sounds great! \$\endgroup\$ – PkmnQ Mar 11 at 5:21
1
\$\begingroup\$

Find the most important character

The challenge is to write a program that outputs the most occurrent non-trivial* character in the input string, excluding these bracketing characters ()[]{}. A solution is scored by feeding the program's source into its input. Bracketing characters are allowed in the program, but may not be selected by the program as the most occurrent character. In cases where letters have the same percentile score, any of the characters can be returned, or all of them.

Write a program that has a maximal percentage of a single non-trivial* character, excluding these bracketing characters ()[]{}. Bracketing characters are allowed, but may not be selected as the highest-percentage character. Answer is scored as by running the program, with the program's source as its own input. In cases where letters have the same percentile score, any of the characters can be returned, or all of them.

*Non-trivial is defined in this case to be a character that contributes to the functionality of the program. If the character can be removed without influencing how the program runs, it is a trivial character.

Scoring

Score is determined as follows:

$$(\frac{n_{char}}{n_{total}}) * 100\% $$

With nchar being the number of occurrences of that character in the input, and ntotal being the total number of non-trivial characters in the input. With this scoring criteria, all scores should be within the range (0,100]

Highest scoring solution per language wins.

Input

Solutions should take in any valid string as input. Scoring is done using the program's source code as input(with all non-trivial charcters removed).

Output

A single character with the highest percentage occurrence. Each solution should be capable of outputting standard ASCII, as well as the language's codepage (if applicable).

Errata

Creative solutions are encouraged. Boring solutions with long padded strings substituted in for numbers are discouraged. Standard loopholes are disallowed.

Examples

Program:

aabbbc

Output:

b


Program:

aabb

Output:

a or b or ab

| |
\$\endgroup\$
  • \$\begingroup\$ Since I don't see it mentioned, you may want to add we should aim for an as high as possible percentage as score. \$\endgroup\$ – Kevin Cruijssen Feb 12 at 8:25
  • \$\begingroup\$ And if I understand it correctly the input is the only possible input for the program? So it won't have to work for other inputs as well (outputting the 'most important' character of that input). \$\endgroup\$ – Kevin Cruijssen Feb 12 at 8:36
  • 1
    \$\begingroup\$ So something like '?? in 05AB1E (push "?" and output it, ignoring the input) would score 66.7%? \$\endgroup\$ – Kevin Cruijssen Feb 12 at 9:01
  • 1
    \$\begingroup\$ You are correct on aiming for the highest score. My intention was that the code should work on any inputs, however scoring is only done on the program source itself. \$\endgroup\$ – JPeroutek Feb 12 at 11:14
  • \$\begingroup\$ Ah ok, that indeed seems better. You may want to clarify that a bit, since at the Input section it now only mentions "The program's source code", hence my confusion. \$\endgroup\$ – Kevin Cruijssen Feb 12 at 11:44
  • \$\begingroup\$ You’re right, that bit is a tad vague. I will update when I get to work. \$\endgroup\$ – JPeroutek Feb 12 at 11:46
  • 1
    \$\begingroup\$ @KevinCruijssen I've edited the challenge to reflect these changes. Does this better reflect the challenge? \$\endgroup\$ – JPeroutek Feb 12 at 13:39
  • 1
    \$\begingroup\$ Yep, that's indeed a lot clearer! :) One more question: can the input potentially contain any unicode character, or is it limited to just printable ASCII and/or the language's used codepage? \$\endgroup\$ – Kevin Cruijssen Feb 12 at 13:41
  • \$\begingroup\$ Hmm, well if the character isn't on the languages codepage then it likely wouldnt be used in a solution right? I'd think that any character that the program can successfully output would be valid. \$\endgroup\$ – JPeroutek Feb 12 at 13:43
  • 1
    \$\begingroup\$ "I'd think that any character that the program can successfully output would be valid." This is different than having to support the entire codepage or extended ASCII, though. I.e. an answer in Unary/Lenguage using a single character and printing that single used character would score 100%, since the only possible input is any amount of that chosen character. And an answer in Whitespace would only have to support spaces, tabs, and newlines as potential input in that case. If that's your intention than it's fine by me, but it's different than allowing the entire codepage as input. :) \$\endgroup\$ – Kevin Cruijssen Feb 12 at 14:06
  • 1
    \$\begingroup\$ Ahh I see the distinction you are making. I'd say that the program should at least be able to printout standard ASCII, as well as the languages codepage. Does that sound reasonable? \$\endgroup\$ – JPeroutek Feb 12 at 14:10
  • \$\begingroup\$ Yep, that indeed sounds as a good solution. \$\endgroup\$ – Kevin Cruijssen Feb 12 at 14:27
1
\$\begingroup\$

Shift the digits

Here, x (supplied as input) and n (the result of your computation) are both positive integers. n * x = n shifted. Find n.

Here's an example of shifting:

123456789 -> 912345678
abcdefghi -> iabcdefgh (letters = any 0~9 digit)
123       -> 312

Rules

  • Preceding zeros count after shifting. If the number is 10 and is multiplied by 0.1 (0.1 isn't a valid input), the result is 1, which isn't equal to 01 (10 after shifting).
  • Your code has to run on Try It Online without timing out.
  • If your number only has one digit, the shifted result is your number:
1 -> 1
4 -> 4
9 -> 9

Test cases

Just to show that it's possible ...

9 -> 10112359550561797752808988764044943820224719
(In this test case, x = 9 and n = 10112359550561797752808988764044943820224719.
n shifted = n * x =              91011235955056179775280898876404494382022471)

Don't believe it? Try it online.

| |
\$\endgroup\$
  • \$\begingroup\$ Is this the point of the challenge: "you hardcode any number you want in your code, I give you a number as input, you multiply your number by mine and right shift it once"? \$\endgroup\$ – Lyxal Feb 16 at 7:29
  • \$\begingroup\$ @Lyxal The challenge should be self-explanatory. Can you understand it now? \$\endgroup\$ – user92069 Feb 16 at 10:01
  • \$\begingroup\$ Aha! So it's "x * n = x shifted, find n". I get it now! \$\endgroup\$ – Lyxal Feb 16 at 10:26
  • \$\begingroup\$ I feel there is something I'm missing. Are you going to give as input only numbers that have a multiple that corresponds to said shifting? \$\endgroup\$ – RGS Feb 16 at 18:06
  • \$\begingroup\$ I've been doing some thinking and I believe that asking to find the smallest possible integer is impossible for numbers which aren't all the same digit. Some test cases would be helpful. \$\endgroup\$ – Lyxal Feb 16 at 20:33
  • \$\begingroup\$ I've seen a really large integer (in a book) that shifts itself right once after being multiplied by 9. If that's really neccecary I'd try to type it here. \$\endgroup\$ – user92069 Feb 17 at 2:46
  • \$\begingroup\$ @Lyxal It's possible, see my test case. \$\endgroup\$ – user92069 Feb 17 at 3:40
  • \$\begingroup\$ @RGS I'm going to give any number that has a multiple; after division of that multiple by that number, the result will be the reverse of the shifting of the number. (I've changed my challenge since Lyxal "got" the formula.) \$\endgroup\$ – user92069 Feb 17 at 3:43
1
\$\begingroup\$

Posted here

| |
\$\endgroup\$
1
\$\begingroup\$

Approximate Alternating Triangles

| |
\$\endgroup\$
  • \$\begingroup\$ I think your added explanation is good, though I admit I still don't see how the resulting image is a triangle. It may just be me, but maybe it would be easier to see if provided a drawing? \$\endgroup\$ – FryAmTheEggman Mar 2 at 0:34
  • \$\begingroup\$ Ah, I see, but why \` (sorry comment markdown is messing that up, just the one backslash...) on the left and not |? You could also try naming it "approximate alternating triangles" or something. \$\endgroup\$ – FryAmTheEggman Mar 2 at 0:41
  • \$\begingroup\$ look less like a triangle Why do you want to make it look _less than a triangle? Why not | to make it look more like a triangle? \$\endgroup\$ – Luis Mendo Mar 4 at 11:45
1
\$\begingroup\$

Japanese Encoding Conversion

| |
\$\endgroup\$
  • \$\begingroup\$ I think switching between hex and decimal in the definitions is more likely to cause confusion than sticking to just one of them. I think you also don't indicate that the tuples you define are bytes that are concatenated to the final result. I'm not sure if I'm misunderstanding, but doesn't the clipping mean converting from shift JIS is ambiguous? Separately, you can use \left and \right to make your brackets the right height. \$\endgroup\$ – FryAmTheEggman Mar 1 at 18:40
  • \$\begingroup\$ @FryAmTheEggman For the Shift_JIS case, the range used is [0x81-0x9F,0xE0-0xEF] for the first byte and [0x40-0x7E, 0x80-0xFC] for the second byte, which is of size precisely 8,836. Since 区 won't exceed 128, and the starting points of 点 in both cases are separated by 95, the first case won't overlap with the second. \$\endgroup\$ – Shieru Asakoto Mar 2 at 3:24
  • \$\begingroup\$ @FryAmTheEggman I wrote kuten in decimal and bytes in hexadecimal because they were so defined; edited to only show in decimal, but keep accepting both decimal and hexadecimal input/output form. \$\endgroup\$ – Shieru Asakoto Mar 2 at 3:36
  • \$\begingroup\$ Ah yes, I see where I made an error now. I think the rewrite you did makes it easier to read. I don't see anything else, though of course I don't speak for everyone. Good luck! \$\endgroup\$ – FryAmTheEggman Mar 2 at 20:06
  • \$\begingroup\$ Typo: monas should be moras. \$\endgroup\$ – Grimmy Mar 6 at 14:24
1
\$\begingroup\$

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ What happens if all integers are equally probable? Is that answer disqualified? Or does it score infinity? I also take it that there is a factor of randomness here, so perhaps you could mention that. \$\endgroup\$ – Lyxal Feb 14 at 6:21
  • 1
    \$\begingroup\$ Of course, I may have missed the mark completely. Are we required to create our own scale of randomness (i.e. our own deviation from uniform randomness if that makes sense)? \$\endgroup\$ – Lyxal Feb 14 at 6:22
  • 1
    \$\begingroup\$ If all integers are equally probably, wouldn't that give a score of effectively 0? (probability of 1/Integer.Max for the "most frequently occuring", which could be any of the integers)? \$\endgroup\$ – simonalexander2005 Feb 14 at 12:08
  • 3
    \$\begingroup\$ @Lyxal It is mathematically impossible for all integers to have equal probability. \$\endgroup\$ – Wheat Wizard Feb 14 at 14:07
  • 3
    \$\begingroup\$ This seems easy to score arbitrarily close to zero. For example, keep generating a random number from 1 to N until you get a 1, and count how many tries it takes before you succeed. To include negative outputs, pick a random sign. Make N large and the score tends to 0. \$\endgroup\$ – xnor Feb 14 at 14:45
  • \$\begingroup\$ @xnor There is a byte limit which stops "arbitrarily close" formulations. Did you miss this or am I missing what you are suggesting? \$\endgroup\$ – Wheat Wizard Feb 14 at 15:28
  • 4
    \$\begingroup\$ You're right, the byte limit stops you from actually getting arbitrarily close to 0. But, I expect there to be plenty of room in 100 bytes to stuff in some ginormous number bust-beaver style, at least in fairly compact languages. So, I think this challenge will mostly come down to "what's the biggest number you can express in 100-X bytes" where X is however many bytes the random part takes. \$\endgroup\$ – xnor Feb 14 at 15:33
  • \$\begingroup\$ My thought is that there are a number of possible things that you would be able to use as the random part each with different drawbacks and strengths. In my mind the challenge is sort of coming up with the random part that best fits the language. There is definitely going to be a big number component to this that is important, but since that has mostly been explored in other challenges I would expect borrowing there. \$\endgroup\$ – Wheat Wizard Feb 14 at 15:36
  • 1
    \$\begingroup\$ What do you think then about the challenge being just to generate a random integer so that each one has nonzero probability? I think that as is, the big number generation is so important to the score that it makes this a chameleon challenge. \$\endgroup\$ – xnor Feb 14 at 15:42
  • \$\begingroup\$ Alternatively, the "big number" N could be an input, and you stipulate that as N grows, the maximum chance of any integer to be chosen must approach zero. \$\endgroup\$ – xnor Feb 14 at 15:43
  • \$\begingroup\$ @xnor I think that I am pretty happy with the challenge as is. I prefer the current challenge over the suggested challenges since this one I feel has an incentive to loosen the distribution whereas I do not feel the others do. The big number generation is important, but I consider that as a more general technique. \$\endgroup\$ – Wheat Wizard Feb 14 at 15:48
  • \$\begingroup\$ Maybe I'm missing something about loosening the distribution. I'm envisioning solutions in a golfing language to be about 7 bytes of "take a number N and make a flat random distribution based on it" and 93 bytes of "generate a huge N". For regular languages with a random() function, maybe split it 25 bytes / 75 bytes. Maybe I'm missing something, but I can't really see a viable strategy that isn't effectively the N-input challenge I suggested but with big number generation code copy-pasted in for N. Do you think there is? \$\endgroup\$ – xnor Feb 14 at 15:59
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – xnor Feb 14 at 16:07
  • 1
    \$\begingroup\$ I would allow for some entropy input to give pure languages a chance. \$\endgroup\$ – Jonathan Frech Feb 25 at 1:16
  • \$\begingroup\$ @JonathanFrech I would like to but it is a little difficult for entropy to make it work. If you have a concrete idea for how I might fairly introduce entropy, I am open to ideas. \$\endgroup\$ – Wheat Wizard Feb 25 at 1:35
1
\$\begingroup\$

Making Minimial Memory Masterpieces

In this challenge you will be asked to write a small computer program to paint an approximation of the painting Fine Wind, Clear Morning.

Your submission

In this challenge we are going to start with a blank canvas. We are going to add an "ant" in the top left corner. You will be telling the ant how to paint the picture by writing its brain.

An ant is a simple creature, at a given time it knows two things.

  • Some memories that it has

  • The color of the pixel it is currently standing on

And at every step the ant consults these two things it knows and then

  1. Draws one pixel of any color where it is standing

  2. Moves one pixel in a cardinal direction

  3. Replaces its all of its memory

The ant can thus be thought of as a function which takes a color and a value and spits out a color, a value and a cardinal direction.

For example here is the brain of an ant that draws a zigzag pattern in red

\$ f(c,m) = \left\{\begin{matrix}(\mathrm{Red}, & \mathrm{South}, & 1) & \mathrm{if} & m = 0\\ (\mathrm{Red}, & \mathrm{East}, & 0) & \mathrm{if} & m = 1\end{matrix}\right. \$

However our canvas is not infinite, so this ant would run into a border eventually. We will stop the ant if it tries to move off, by canceling its move and leaving it on the square it is on. You are free to use this behavior to your advantage.

The one issue here is that currently the ant will never stop, it will just keep painting forever. Which is why ants come with a builtin kill switch. When an ant's memories are equal to an exact value the ant explodes or something, ending the drawing.

Your submission will thus consist of 3 things

  • The starting memory for your ant

  • A description of the ant's function (more on this later)

  • The ending memory for your ant

Scoring

The goal of this challenge is to have the ant that requires the least memory to operate. We will count this by the number of different states your ant's memory can have.

Thus to score your answer you should run it on the canvas provided. Once the ant has finished your score will be the total number of distinct memories used by your ant through the process. We will include the initial memory even if it does not appear again, but you should not count the ending memory (the one that kills the ant).

The lowest score will be the winner.

The painting

The painting will be a low resolution version of the one from the wikipedium. It will use 3 bit color resolution.

I will decide on the exact specific sizes and make the image in a bit.

A valid answer must produce this image exactly when run on the canvas.

Verification Tool

I will make a tool for running and verifying programs, using a standardized format. It will be runnable in browser.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I assume based on the scoring the ant is invalid if it fails to paint exactly the required picture? \$\endgroup\$ – FryAmTheEggman Mar 9 at 20:37
  • \$\begingroup\$ @FryAmTheEggman Yes thank you. That also reminded me of another thing I forgot to say in the challenge. \$\endgroup\$ – Wheat Wizard Mar 9 at 20:47
1
\$\begingroup\$
| |
\$\endgroup\$
  • 2
    \$\begingroup\$ Interesting challenge, looks solid. Will there always be at least one empty column between lines or lane dividers, as seems to be in all examples? \$\endgroup\$ – xnor Mar 10 at 11:08
  • 1
    \$\begingroup\$ With your new clarification, can there be two adjacent lines? Also, can there be an input with just one line, or just empty space? Are trailing empty spaces a possibility? \$\endgroup\$ – xnor Mar 10 at 11:59
  • \$\begingroup\$ I meant in the input, but I guess whether the output can add or omit them could also be a question. \$\endgroup\$ – xnor Mar 10 at 12:12
  • 1
    \$\begingroup\$ Yes, I think you answered everything. So, if I got this right, I think this is a uniquely-matching regex of all valid inputs as sequences of columns, with e,l,d indicating empty, lane, and divider: e*(le(e|d)*e|le|l)*le*|e*. \$\endgroup\$ – xnor Mar 10 at 12:26
  • \$\begingroup\$ @xnor Took a little work to analyze but I think it is. \$\endgroup\$ – Wheat Wizard Mar 10 at 12:39
1
\$\begingroup\$

Golf yourself a real calculator [draft]

We will only cover the characters(0123456789+-*/=%ñ) in our tutorial.

The = operations

Unlike most desktop calculators, our household calculator is a tacit language. Therefore it is able to do a lot more than other infix calculators.

Take a simple calculation as an example. The non-scientific calculator does not have the exponentiation operator. What do you do to calculate 2^5?

2*2====

However, there's a shortcut for doing that. Since 2 is already in the expression buffer, you can simply do

2*====

The calculator automatically fills in the current expression during the inputting.

Here is a demonstration of how this works:

(A template for easy copy&paste.

Pressed Key      : 
Expression buffer: 
Output buffer    : 
)

Pressed Key      : 2
Expression buffer: 2
Output buffer    : 2

Pressed Key      : *
Expression buffer: 2 *
Output buffer    : 2

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 4

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 8

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 16

Pressed Key      : =
Expression buffer: * 2
Output buffer    : 32

Implicit 0 before calculation

Suppose you enterede the following expression:

*1

Now, don't get me wrong, the household calculator of course doesn't have pointers. So, why doesn't it raise a syntax error though? (The output is 0 by the way.) Here's why.

The calculator initially has the expression starting at 0, therefore it prepends a 0 to the expression. Therefore the full form of our expression is:

0*1

What we've learned so far

  • The output buffer is a part of the calculator storing the latest-evaluated integer. All entered numbers get appended to the output buffer as well as the expression buffer.
  • The expression buffer is a part of the calculator storing the latest instruction. After a = operator, it stores the latest applied expression for later application.
  • The = operator tries to evaluate the instruction buffer. If that's a syntax error, it tries to evaluate that concatenated the output buffer. If that still fails, it tries to evaluate the output buffer concatenated with the instruction buffer. After that operation, the expression starting from the newest-entered dyadic operator is saved in the expression buffer.
| |
\$\endgroup\$
1
\$\begingroup\$

Mimic the X11 Primary selection

Background

In X11 (a windowing system used by a lot of Unix-like OS), what you would call the clipboard behave a bit differently than on other OSes like MacOS or Windows. While the "traditional" clipboard using ctrl+v/ctrl+c works, there is also another clipboard, called PRIMARY selection, that behave as following:

  • when you select a piece of text, this selection is added to the clipboard
  • when you use the middle mouse button, the content of that selection is pasted where your mouse is.

Some more details for those who are interested : X11: How does “the” clipboard work?

Challenge

The input in this challenge is any representation of a binary input. In the following I will use 'S' for select and 'P' for paste.

Given the input, you must output the input after making the following changes :

  • put the content of the current output in the primary selection when you receive a select instruction
  • paste the content of the primary selection in the middle of the current output when you receive a paste character. If the current output is odd numbered, the middle is the length divided by 2 and truncated.

Example

Input is SPSP :

selection = ""
output = "SPSP"
 SPSP
↑
selection = "SPSP"
output = "SPSP"
 SPSP
 ↑
selection = "SPSP"
output = "SPSPSPSP"
 SPSP
  ↑
selection = "SPSPSPSP"
output = "SPSPSPSP"
 SPSP
   ↑
selection = "SPSPSPSP"
output = "SPSPSPSPSPSPSPSP"
 SPSP
    ↑

Final Output is SPSPSPSPSPSPSPSP

Test Cases

"" -> ""
"S" -> "S"
"P" -> "P"
"PS" -> "PS"
"SP" -> "SSPP"
"SPP" -> "SSPPSPPPP"
"SPSP" -> "SPSPSPSPSPSPSPSP"
"SPPSP" -> "SPSPPSPSPSPPSPPSPSPPSPPSPSPPSP"
"SPPSPSSS" -> ""SPPSSPPSSPPSSPPSSPPSSPPSPSSSPSSSPSSSPSSSPSSSPSSS

Reference Implementation

In Python 3 :

def clipboard(inp, select="S", paste="P"):
    out = inp
    primary_selection = ""
    for instruction in inp:
        if instruction is select:
            primary_selection = out
        if instruction is paste:
            out = out[:len(out)//2] + primary_selection + out[len(out)//2:]
    return out

Try it online!

Rules

  • You may assume that the input contains only the "paste" or "select" characters (you don't need to handle error cases)
  • You may use any kind of data representation (e.g binary data is allowed.)
  • Standard code-golf rules , shortest submission by bytes wins!
| |
\$\endgroup\$
  • \$\begingroup\$ Can we take the input newline-separated? (so like S\nP\nP\nS\nP) \$\endgroup\$ – user41805 Mar 15 at 8:23
  • \$\begingroup\$ @user41805 I would say that it is allowed. I would also allow using \n (or any whitespace) as either a "paste" or "select" character. \$\endgroup\$ – Lescurel Mar 16 at 18:42
1
\$\begingroup\$

Four Divisors

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Test Case 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7

The answer is the sum of divisors of 21 only.

Please feel free to add more test cases.

This is code-golf so shortest submission in bytes wins! If you liked this challenge, consider upvoting it... And happy golfing!

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ When posting, please change your post to only contain a link to the main post, then delete. \$\endgroup\$ – Adám Mar 24 at 14:23
  • \$\begingroup\$ Then delete, post in meta??? \$\endgroup\$ – Pluviophile Mar 24 at 14:56
  • \$\begingroup\$ No, post, then delete from meta. \$\endgroup\$ – Adám Mar 24 at 15:10
  • \$\begingroup\$ @Adam Please let me know, how long to wait for the post before posting it in main site. For better results. \$\endgroup\$ – Pluviophile Mar 24 at 15:20
  • \$\begingroup\$ I usually wait for a week, to catch those that stop by on a weekly basis, e.g. because they only visit while (not) at work. When I see a bunch of people in TNB, I also ask them to review. \$\endgroup\$ – Adám Mar 24 at 15:22
  • \$\begingroup\$ What is TNB? Sorry for asking, I'm new to Code-golf \$\endgroup\$ – Pluviophile Mar 24 at 15:25
  • \$\begingroup\$ The Nineteenth Byte chat room. Also, check out this list. \$\endgroup\$ – Adám Mar 24 at 15:26
  • \$\begingroup\$ What else can I do to improve the challenge?? \$\endgroup\$ – Pluviophile Mar 24 at 15:26
  • \$\begingroup\$ Too late now that you've posted to main already. Expect downvotes :-( \$\endgroup\$ – Adám Mar 24 at 15:26
  • \$\begingroup\$ If U don't mind. Please do check "Check if There is a Valid Path in a Grid" and provide any feedback/suggestions that I can use to improve the challenge \$\endgroup\$ – Pluviophile Mar 24 at 15:28
  • \$\begingroup\$ OK, but I'm a bit busy (working) atm. Hence the advice to leave for a while in the sandbox. \$\endgroup\$ – Adám Mar 24 at 15:28
  • \$\begingroup\$ Yeah sure.. Your feedback and suggestions are very valuable. Thank you. For guiding a newbie... \$\endgroup\$ – Pluviophile Mar 24 at 15:38
1
\$\begingroup\$

RRE numbers

Given a single floating-point number (which can potentially be taken as a string), output whether this decimal is an RRE number.

RRE complement for the input number

Say your input is 3.14.

  1. Replace the decimal point by the fraction bar. 3/14
  2. Reciprocal the fraction. 14/3
  3. Evaluate the fraction. 4.666...
  4. Round the decimal point to the same length as the input. 4.67
  5. If the absolute difference between the input and the output is below 2, it's an RRE number. Otherwise, it isn't an RRE number.

Specification

  1. Programs are allowed to give wrong output if the absolute difference is very close to 2.
  2. The integral part of the decimal is always nonzero.
  3. Truthy/Falsy outputs follows the language's convention, or exactly one value for truthy and another for falsy.

Test cases

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

1.0     -> True
2.9     -> True
3.14    -> True
50.2501 -> True
2.14    -> False
2.11111 -> False
3.1     -> False
51.123  -> False
51.51   -> False
24.12   -> False
| |
\$\endgroup\$
  • \$\begingroup\$ 1) Rounding 4.666... to two decimal places gives 4.67. 2) Floating-point numbers are always subject to precision issues. I think it's best to let the programs take a string representation as input, and state that "programs are allowed to give wrong output if the absolute difference is very close to 2". 3) If the integral part is 0, the algorithm will invoke division by 0. Is handling it part of the challenge? \$\endgroup\$ – Bubbler Mar 27 at 6:07
  • \$\begingroup\$ 4) For truthy/falsy, it currently reads like I can output the input as-is and say "the program's output format is a RRE number for truthy, a non-RRE number for falsy". What I use is "truthy/falsy following the language's convention, or exactly one value for truthy and another for falsy". \$\endgroup\$ – Bubbler Mar 27 at 6:13
  • \$\begingroup\$ I don't see how restricted source will fit here. Btw, a big truthy test case: 50.2501 \$\endgroup\$ – Bubbler Mar 27 at 6:39
  • \$\begingroup\$ @Bubbler Ahh, the challenge is just about checking whether the square of the integral part is close to the the decimal part. Should I post it? \$\endgroup\$ – user92069 Mar 27 at 6:43
1
\$\begingroup\$

Excessively complicated Game of Life

In the excessively complicated version of the Game of Life, the world is a \$W \times H\$ square torus with a grid of squares. Each square has a rulestring attached to it - by default, B/S. Each square has a dead or alive cell in it. Each alive cell is controlled by a player. Every turn, if there is not an alive cell in a square, it is born iff the part between B and / contains the number of alive neighbours. Every turn, if there is an alive cell in a square, it survives iff the part after S contains the number of alive neighbours. Cells are considered adjacent if they have a common edge or a corner. A cell is not adjacent with itself. Cells controlled by other players also count as alive neighbours.

For example, normal Conway's Game of Life cells have the B3/S23 rulestring: cells are born if they have exactly 3 alive neighbours, and survive if they have 2 or 3.

Each player starts with a B/S012345678 cell, placed uniformly randomly.

Each cell knows a 3x3 array of numbers from \$-1\$ to \$1\$, representing adjacent cells (including self). \$1\$ in it means an ally cell, \$0\$ means a dead cell, and \$-1\$ means an enemy cell, and a 3x3 array of rulestrings for adjacent cells.

Every turn, every cell can alter one bit of the rulestring of any adjacent square (including its own) - that is, remove or add a number from it (or, alternatively, it can do nothing).

When cells are born, the player they belong to is chosen semi-randomly: the odds of the cell being assigned to a player are proportional to the number of cells they contributed to the cell's birth.

A player is eliminated when all their cells die. When \$N\$ turns passed, or when only one player remains, the game ends. A full point is distributed between all remaining players proportionally to the number of cells they control (dead cells don't count).

Clarifications

  • Rulestrings are attached to squares, not to cells. When a cell dies, the rulestring on its square is not changed.
  • No cell can be born with zero alive adjacent cells (that is, rulestrings cannot start with B0).
  • When multiple cells attempt to alter the same bit in a rulestring, it is only affected once.

Challenge

Define a pure function \$(nearbyStates, nearbyRules)\to(\Delta x, \Delta y, index)\$ to be used as the algorithm for your cells. To do nothing, output an index of 0.

Otherwise, an index of 1 corresponds to toggling B1, 2 to B2 and so on until B8, the index 9 is skipped, then an index of 10 corresponds to toggling S0, 11 to S1 and so on until S8.

Winning criterion

\$X\$ games are run, and the leaderboard is formed by sorting participants by the total number of points.

This is , so whoever wins wins!

Sandbox stuff

  • Is this a good idea?
  • Is the description of the game clear?

I think I decided that the language for submissions will be Javascript. Now I have to write a controller.

Besides the obvious Javascript option, I am considering C++ with a Javascript engine (probably V8). This can multiply the performance by \$\%NUMBER\_OF\_PROCESSORS\% \cdot \frac{cppPerformance}{jsPerformance} \cdot \frac{myC++skill}{myJSskill}\$, which can be quite large. Unfortunately, that might also muptiply the challenge's popularity by \$\frac{webBrowserLoadingSpeed}{programInstallationSpeed}\$, which can be quite small! Would that be a good idea?

| |
\$\endgroup\$
  • \$\begingroup\$ Disclaimer: I'm biased in both categories. Language: Leaning towards JS, especially since this challenge seems to be of the "hack around and see what works" type, and I believe browser-based ones shine here the most. Python seems to be popular as well, but AFAIK it's usually used for challenges that don't need rich visualization. Other languages, like Java, .NET, C++, etc., can also be considered, of course (higher performance)... Orientation: Removing orientation does seem to be a good fit. It increases the amount of interactions that can happen between any two entries. \$\endgroup\$ – Alion Mar 26 at 18:31
  • \$\begingroup\$ Regarding C++: You can have your cake and eat it too. Have you heard of Wasm and Web Workers? This combination lets you get near-native peformance along with multithreading all in the browser. \$\endgroup\$ – Alion Mar 29 at 13:40
  • \$\begingroup\$ Note that improving controller performance only gets you so far. You're gonna have to go the Formic route and cache entry responses in some smart way to extract all the potential of C++. \$\endgroup\$ – Alion Mar 29 at 13:48
  • \$\begingroup\$ @Alion I include "caching in some smart way" in "improving controller performance". I have also considered using Emscripten (and started using it, starting with the renderer first, because I randomly decided so) but then I got worried because I thought calling JS from WASM and WASM from JS is going to be too slow. After reading the comment, I googled and it turned out Emscripten has multithreading. I guess I'll continue now. \$\endgroup\$ – the default. Mar 29 at 13:50
  • \$\begingroup\$ I'd like to see a good C/C++ KoTH. I'm always excluded from them because I don't know any languages that they're in. \$\endgroup\$ – S.S. Anne Apr 1 at 20:15
  • \$\begingroup\$ @SSAnne I do not understand your comment. Are you proposing a C/C++ KoTH, or are you stating that they cannot be good because you don't know these languages? \$\endgroup\$ – the default. Apr 2 at 0:09
1
\$\begingroup\$

Are these the same time?

Context

When asked about the time (i.e. hours and minutes), people naturally reply with any one of a given set of fairly common sentences:

  • (A) it is M past H
  • (B) it is M to H
  • (C) it is H minus M

Where M above refers to some amount of minutes and H to some amount of hours. Concrete corresponding examples, all referring to the time 3:40 pm:

  • (A) it is 40 past 3
  • (B) it is 20 to 4
  • (C) it is 4 minus 20

Task

Given two of these sentences, output a Truthy value if they represent the same time and a Falsy value if they do not.

Input

Your input will be two sentences of the above, where references to minutes will always be rounded to the nearest multiple of 5 (i.e. the minutes will always be one of 5, 10, 15, 20, ..., 50, 55.

Because all sentences start with "it is " you may ommit that from your input sentences.

Output

A Truthy value if the two times are the same, a Falsy value otherwise.

Test cases

Here is a sample program for checking the test cases.

Sandbox

Should the minutes and hours in the input com as integers instead of English words?

| |
\$\endgroup\$
  • \$\begingroup\$ Interesting challenge. Yes, the minutes and hours in the input should come as integers. Otherwise, this becomes a chameleon challenge that appears to be about parsing relation words, but actually is about parsing English numbers. I think you can make the challenge more interesting by adding (D) it is H M. Please address 1) how to distinguish AM/PM or that we don't need to, 2) how to deal with roll-overs like "5 to 0", and 3) if H and M have upper and lower bounds. \$\endgroup\$ – Adám Apr 1 at 6:29
  • \$\begingroup\$ I kid you not, I have never heard any one call it "H minus M". Still, I agree with @Adám that y'all need to ensure that input and output formats are what I like to call "reasonable and convenient", with extra emphasis on the "convenient" part. \$\endgroup\$ – Lyxal Apr 1 at 6:52
  • 1
    \$\begingroup\$ @Lyxal Me neither. But actually, that can be fixed by changing "minus" to "in", as in "4 in 20 [minutes]" \$\endgroup\$ – Adám Apr 1 at 6:55
  • \$\begingroup\$ An alternative you might consider to checking if two sentences represent equal times, is to have code take just one and produce any "canonical form" of it, such that the canonical form can be anything where two inputs give the same canonical form if and only if they are equal. \$\endgroup\$ – xnor Apr 1 at 9:15
  • \$\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. The feedback is very good and I will take care of it, but I prefer to do it myself so I can do the changes I see necessary: e.g. if I am accepting hours and minutes as integers, I no longer want the minutes to be in the set 5, 10, 15, ..., 55. \$\endgroup\$ – RGS Apr 1 at 11:48
1
\$\begingroup\$

\$\Theta(N\cdot\sqrt N)\$ sort

The challenge is to write a program that sorts an array of distinct positive integers in ascending order. You may input the array and output the result using the default IO methods.

However, the worst-case time complexity of the algorithm used must be \$\Theta(N \cdot \sqrt N)\$, where \$N\$ is the length of the input array.

You may not assume your built-in sorting functions to have any time complexity in particular. While you can implement a fast (e.g. \$O(N \log N)\$) sort and then perform pointless operations to increase the complexity, direct algorithms exist.

This question is tagged , so the shortest code wins!

Sandbox stuff

I have noticed that a possible solution is, for example, to create a sorted multiset from the array and read it back. I would probably like to disallow that. Is there a way to achieve that without making the validity criteria subjective?

| |
\$\endgroup\$
  • \$\begingroup\$ I feel like this will be answered by implementing sorting efficiently, then doing something pointless for the required number of steps. \$\endgroup\$ – xnor Apr 1 at 8:55
  • \$\begingroup\$ @xnor That would involve implementing a O(n log n) sort or radix sort, which can be more complicated than a O(n*sqrt(n)) algorithm. There's, for example, a gap sequence that results in O(n * sqrt(n)) complexity for Shellsort. \$\endgroup\$ – the default. Apr 1 at 9:04
1
\$\begingroup\$

Similar Numbers

posted

| |
\$\endgroup\$
1
\$\begingroup\$

Modify The Stack

Posted

| |
\$\endgroup\$
  • \$\begingroup\$ Specifying that the first element is the top of the stack could help understanding the challenge a lot. Can we use some other values instead of the stack elements a, b, c and/or the commands s, d, t? Also, the operation a b c -> b c a is often called rotate or roll. \$\endgroup\$ – Bubbler Mar 30 at 2:38
  • \$\begingroup\$ For test cases: a c b is tts. a b a b c can be done with dtdtt or dtdts. \$\endgroup\$ – Bubbler Mar 30 at 2:41
  • \$\begingroup\$ thanks, but dtdtt and dtdts doesn't work. \$\endgroup\$ – Command Master Mar 30 at 5:29
  • \$\begingroup\$ Sorry, I had the t operation mistaken, but your tdtsdt doesn't work either. The first operation should be s. \$\endgroup\$ – Bubbler Mar 30 at 5:39
  • \$\begingroup\$ right, I fixed that \$\endgroup\$ – Command Master Mar 30 at 5:46
  • \$\begingroup\$ I don't think the test cases are very helpful here until they are actually proven optimal... Do you really want to require input validation? If so, it is probably a very bad idea to post this without writing a reference implementation to make sure it's possible and not too annoying. (besides: I silently downvoted before because I simply dislike the idea, and not because of some specification issues, so I had nothing to comment) \$\endgroup\$ – the default. Apr 5 at 16:05
  • 1
    \$\begingroup\$ @mypronounismonicareinstate Sandbox is all about feedback. Silent downvotes don't help the challenge writer and the community. If you don't like the whole idea, you could say so in the comments in the first place (preferably with why you think that way), and then the challenge writer could consider to rewrite it or abandon it and try out something different. \$\endgroup\$ – Bubbler Apr 5 at 23:25
1
\$\begingroup\$

Compactify the input

Posted

| |
\$\endgroup\$
  • \$\begingroup\$ Off topic: BASIC programmers were often recommended to name their variables this way. \$\endgroup\$ – user92069 Apr 8 at 14:26
  • \$\begingroup\$ I agree that it's better to compress a single word instead. \$\endgroup\$ – user92069 Apr 8 at 14:26
  • \$\begingroup\$ hmm ok, I'll do that \$\endgroup\$ – Command Master Apr 8 at 17:42
  • \$\begingroup\$ I think the mention of compression and natural language is misleading, since it leads the reader to expect some compression based on the statistical properties of text. \$\endgroup\$ – xnor Apr 8 at 18:36
  • \$\begingroup\$ hmm ok, do you have an idea for a better name? \$\endgroup\$ – Command Master Apr 9 at 4:53
  • \$\begingroup\$ Do you think Compactify the name is a good idea? \$\endgroup\$ – user92069 Apr 9 at 8:44
  • \$\begingroup\$ Related. \$\endgroup\$ – user92069 Apr 9 at 8:46
  • \$\begingroup\$ yes, I like that name, maybe Compactify the input though? As it doesn't have to be a name \$\endgroup\$ – Command Master Apr 9 at 9:02
  • 2
    \$\begingroup\$ I like Compactify the input \$\endgroup\$ – xnor Apr 10 at 12:12
  • \$\begingroup\$ Just an FYI, the regex \B[aeiou] matches each character to be removed. You may receive a lot of answers that are basically just that. \$\endgroup\$ – FryAmTheEggman Apr 12 at 5:10
1
\$\begingroup\$

In need of title.

Note: In the final challenge \$N\$ will be a concrete number (I am thinking about 100), but while this is in the sandbox it is subject to change so I have left it as \$N\$.


This challenge is based off of a list of \$N\$ Castilian (also called Spanish) words and the words they originate from.

You are to write a program or function which takes the origin word as input and outputs as close as possible the Castilian derivative. Your program should be no longer than \$N\$ bytes.

Scoring

To calculate your score run your program on every origin word and calculate the distance between your output and the correct answer. Your score is the sum of all these distances.

The distance here is a modified version of Levenshtein distance. It is the same as Levenshtein distance except replacement steps that add or remove a diacritic cost only 1/2 of a step as opposed to their normal 1.

You can use this code to calculate the distance between two strings.

The goal is to have as low a score as possible.


About the list

All of the origin words spare 1 are Latin words (Late or Classical depending on the word). The one exception is ezkerra (the origin for izquierda) which is of Basque origin. It has been added as an extra curve-ball in case you can get all the others with a little space to spare.

Verbs are always in the infinitive form and nouns in the nominative singular.

The words are not chosen randomly but rather I have focused on choosing words that follow a number of simple rules. The list is also organized so that words that undergo similar transformations are grouped together. This is for your ease of use, nothing more.


The list

profundus, profundo
fundus, hondo
fabulare, hablar
furnus, horno
ferrum, hierro
filus, hijo
folia, hoja
fovea, hoyo
formica, hormiga
facienda, hacienda
factum, hecho
octo, ocho
noctu, noche
lacte, leche
capere, caber
sapere, saber
lupus, lobo
pater, padre
mater, madre
liber, libro
thema, tema
theatrum, teatro
thesaurus, tesoro
thorax, tórax
aether, éter
anthropologia, antropología
orthographia, ortografía
philosophia, filosofía
materia, materia
resistentia, resistencia
aurum, oro
taurus, toro
autumnus, otoño
annus, año
scribere, escribir
scutum, escudo
scutella, escudilla
scriptor, escritor
ezkerra, izquierda
| |
\$\endgroup\$
  • \$\begingroup\$ I think it's interesting in that it should be near impossible to get a perfect score without built-ins. As a suggestion I'd remove the non-ASCII words, or at least normalise them, and perhaps not let \$N\$ be too high. Also, I wonder what the default cat program would be. \$\endgroup\$ – Jo King Mar 3 at 12:31
  • \$\begingroup\$ @JoKing I am looking to somewhat twart perfect scores, I feel there should always be some room for improvement, It just is a little hard to balance this with golfing-languages ability for expressiveness. I am interested to hear what ranges for \$N\$ you think are too high. I started out by avoiding any non-ASCII characters, but it was really hard to build up a representative corpus of words. Plus the accents and eñe really are a feature of the language. I may adjust the scoring so that i and í for example are only half away from each other so that the penalty is small. \$\endgroup\$ – Wheat Wizard Mar 3 at 13:05
1
\$\begingroup\$

How Many Ways To Empty The Glove Box?

Posted

| |
\$\endgroup\$
1
\$\begingroup\$

Compress Numbers

Write two programs, a compressor and a decompressor.

The compressor

  • The compressor will accept a sequence of integers of any value from 0 to 263-1, expressed in any convenient format.
  • You may specify the required format as long as any arbitrary sequence of integers in the required range may be expressed in this format.
  • Behaviour is undefined for any input that does not conform to your required format.
  • The output will be a self contained sequence of bytes.

The decompressor

  • The input will be an unmodified sequence of bytes produced by a valid input to the compressor.
  • Behaviour is undefined for any other sequences of bytes.
  • The output will be the same input to the compressor program that produced the provided sequence of bytes.

Judging

The winning entry will be the valid entry that produces the smallest intermediate sequence of bytes for a sequence of integers that will be produced by the question setter that will be revealed after some number of entries have been submitted and only entries submitted prior to that reveal will be eligible to win.

This sequence will be generated by joining these following sequences into a single sequence and then randomly shuffling that single sequence.

  • 1000 repetitions of the same randomly selected number from 0 to 9.
  • 1000 repetitions of the same randomly selected number from 262 to 263-1.
  • For each x in (8, 16, 32, 63):
    • 1000 random numbers from 0 to 2x-1.

The question setter will answer the challenge with GZIP/GUNZIP at the highest compression setting with no additional processing. If that entry wins, the glory of winning will belong to the authors of GZIP.

Tie-Breaker

If two or more entries produce produce byte sequences of the same size, the following criteria will decide the winner:

  1. If one of those entries is the GZIP entry posted by the question setter, that entry will win.
  2. The entry with the highest voting score wins.
  3. The entry posted first wins.
| |
\$\endgroup\$
1
\$\begingroup\$

Reconstruct an image from columns

You are given an image with all pixel-wide columns shuffled. The challenge is to attempt to reconstruct the image.

[image gallery of varying difficulties]

Sandbox stuff

or (probably asking for fewest inversions)?

Random thought: if rearranging the pixels was similar to the assignment problem, this seems to be similar to the traveling salesman problem.

| |
\$\endgroup\$
1
\$\begingroup\$

A065825

(This is A065825.) The defaults apply, so you can pick another format other than this one.

Given an input integer n, find the smallest number k so that there exists an n-item subset of {1,...,k} where no three items form an arithmetic progression.

Procedure

Here, we calculate A065825(9).

We assume you have already looped from 1 to 19, and k=20 (it's just an example).

1. Generate a range from 1 to k.

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

2. Pick n items from that sequence, following the original order of the sequence.

[1 2 6 7 9 14 15 18 20]

3. No 3 items form an arithmetic progression.

If a sequence has arithmetic progression, it basically means the sequence has the same step between every two consecutive items.

For example, the sequence of positive even numbers ([2 4 6 8 ...]) has a consistent step (i.e. 4-2=2, and 6-4=2, etc.), so it has arithmetic progression.

The Fibonacci sequence ([1 1 2 3 5 8 13 21 ...]) does not have arithmetic progression, since it does not have a consistent step. (3-2=1, 5-3=2, 8-5=3, etc.)

As an example, let's pick 3 items from our generated sequence.

[1 2 6 [7 9 14] 15 18 20]

The picked 3-item sequence does not have arithmetic progression, since the differences are respectively 9-7=2 and 14-9=5.

This has to apply to every 3-item pair:

[[1 2 6] 7 9 14 15 18 20] (2 -1 =1, 6 -2 =4)
[1 [2 6 7] 9 14 15 18 20] (6 -2 =4, 7 -6 =1)
[1 2 [6 7 9] 14 15 18 20] (7 -6 =1, 9 -7 =2)
[1 2 6 [7 9 14] 15 18 20] (9 -7 =2, 14-9 =5)
[1 2 6 7 [9 14 15] 18 20] (14-9 =5, 15-14=1)
[1 2 6 7 9 [14 15 18] 20] (15-14=1, 18-15=3)
[1 2 6 7 9 14 [15 18 20]] (18-15=3, 20-18=2)

Here are some examples of picking non-consecutive items from the output sequence:

[1 [2] 6 [7] 9 [14] 15 18 20] (7-2=5,14-7=7)
[[1] 2 6 [7] [9] 14 15 18 20] (7-1=6,9 -7=2)

If the above is satisfied for k, then k is a valid output for A065825(9).

Meta

Do you think this challenge should be splitted into separate challenges? It seems that it is a single sequence on OEIS.

Test cases

Here is a reference program I use to check my test cases.

n       a(n)
1       1
2       2
3       4
4       5
5       9
6       11
7       13
8       14
9       20
| |
\$\endgroup\$
1
\$\begingroup\$

Are these two DFAs equivalent?

Two Deterministic Finite Automata or DFAs can be checked to see if they accept same set of strings in polynomial time. See section 3.3 of this for a long list of methods and this SO question/answer for a much shorter list.

Input

Your input will be two DFAs. In order to be able to test your code, it needs to be able to handle DFAs 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 "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 are also allowed. Initial and Accepting are, respectively, the lists of initial and accepting states.

For example:

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

This has transition table:

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

And diagram:

enter image description here

It is equivalent to:

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

which has diagram:

enter image description here

A more complicated example:

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

has diagram:

enter image description here

It is equivalent to:

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

with diagram:

enter image description here

More example of equivalent DFAs

1.

Automaton("det",18,4,[ [ 2, 2, 6, 10, 2, 6, 7, 16, 14, 10, 18, 14, 7, 14, 15, 16, 7, 18 ], [ 3, 3, 7, 11, 3, 7, 15, 11, 7, 17, 15, 18\
, 18, 7, 15, 17, 15, 15 ], [ 4, 4, 8, 7, 4, 13, 15, 15, 16, 7, 8, 7, 15, 7, 15, 15, 16, 13 ], [ 5, 5, 9, 12, 5, 14, 7, 13, 9, 14, 17, 12, \
13, 14, 15, 7, 17, 7 ] ],[ 1 ],[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18 ])
Automaton("det",16,"abcd",[ [ 1, 2, 15, 15, 5, 6, 7, 7, 6, 2, 16, 12, 12, 16, 15, 16 ], [ 1, 3, 1, 7, 9, 15, 1, 1, 15, 8, 7, 3, 8, 15, 1, \
15 ], [ 1, 1, 2, 1, 13, 4, 4, 10, 10, 1, 15, 15, 15, 2, 1, 15 ], [ 1, 15, 3, 4, 5, 16, 15, 3, 14, 4, 11, 16, 11, 14, 15, 16 ] ],[ 5 ],[ 2,\
 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ])
    2.
Automaton("det",50,4,[ [ 2, 2, 9, 13, 17, 9, 13, 17, 9, 24, 28, 30, 13, 33, 36, 30, 17, 9, 13, 9, 13, 39, 30, 24, 25, 44, 42, 28, 24, 30, 47, 39, 33, 50, 36, 36, 42, 46, 39, 25, 24, 42, 43, 44, 36, 46, 47, 42, 25, 50 ], [ 3, 6, 10, 14, 18, 10, 14, 20, 10, 25, 14, 10, 32, 34, 34, 38, 20, 10, 14, 10, 14, 38, 10, 25, 43, 34, 25, 45, 46, 10, 32, 49, 34, 43, 34, 49, 50, 50, 49, 50, 46, 25, 43, 49, 49, 50, 45, 50, 43, 43 ], [ 4, 7, 11, 15, 19, 11, 15, 21, 22, 26, 26, 31, 15, 11, 25, 15, 21, 11, 15, 11, 15, 40, 15, 40, 43, 43, 44, 26, 26, 15, 44, 31, 41, 26, 47, 25, 25, 22, 40, 43, 40, 25, 43, 43, 47, 41, 44, 44, 44, 40 ], [ 5, 8, 12, 16, 5, 12, 16, 8, 23, 27, 29, 12, 23, 35, 37, 16, 8, 12, 16, 12, 16, 41, 23, 42, 25, 40, 27, 27, 29, 23, 48, 45, 37, 49, 35, 42, 37, 48, 42, 40, 41, 42, 43, 25, 45, 37, 27, 48, 49, 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, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50 ])
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 ])

3.

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

4.

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

5.

A pair of equivalent DFAs

Non-equivalent DFAs


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

Score

This question is and . Your code must be able to run all the test cases in less than a minute on TIO.

| |
\$\endgroup\$
1
\$\begingroup\$

Island Rose Breeder

Island Roses have an extremely simple genetic code, with just 4 genes: R, Y, W, and B, each with two alleles. This means their entire genome can be represented by four 2-bit gene pairs of the form: 00-00-00-00 (01 and 10 are equivalent)

Island Roses can be bred together. When two roses are bred, each parent flower donates one allele for each gene. This can be represented by Mendelian genetics via a Punnett square:

enter image description here

For instance, a 01-00-11-11 flower that is bred with a 01-00-11-11 flower will result in either:

  • a 00-00-11-11 flower (25% chance)
  • a 01-00-11-11 flower (50% chance)
  • a 11-00-11-11 flower (25% chance)

Based on their genes, Island Roses can display one of 8 phenotypes -- colors.

A list of the genotypes and their corresponding phenotypes can be found here.

Challenge

Given a starting stock of Roses, determine how many generations (and which Roses to use) it would take to breed a particular phenotype.

Because genetic testing is expensive, you can only identify the results of breeding by observing the phenotype of the offspring. For example, Breeding two 11-00-00-01 (Red) roses gives three distinct phenotypes, so any Black rose that results must have genotype of 11-00-00-11.

In the case of ambiguous phenotypes, subsequent generations of breeding can be done to disambiguate the specific phenotypes.

Example Input Roses:

  • 11-00-00-01
  • 00-00-01-00
  • 00-11-00-00

Target Phenotype:

  • 11-11-11-00
| |
\$\endgroup\$
  • \$\begingroup\$ Could you add some examples of what output should look like? Some test cases showing input -> output would also be helpful. Finally, make sure to mention the winning criteria (eg. if it's Code Golf, you should explicitly mention that) \$\endgroup\$ – math junkie Apr 25 at 21:28
1
46 47
48
49 50
99

You must log in to answer this question.

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