459
\$\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\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2562 Answers 2562

1
\$\begingroup\$

Sandbox notes

  • Is there anything that is unclear?

Double Language Supersets

For the purposes of this challenge:

  • A language is a partial mapping from programs (strings of bytes) to outputs (streams of bytes). Not every output must be finite or produce any elements before looping indefinitely.
  • A language L is an superset of another language K if, for every program of length n given meaning in K, there is a program of length n given meaning in L which produces the same output. In other words, all programs in K can be translated into L without requiring any more bytes.

(cops' part)

As a cop, you must:

  • Find two languages, and provide (or link to) a specification in the form of a detailed description or an implementation. Be prepared to answer any questions should ambiguities arise.
  • Define a new "solution" language which is a superset of both of the others. This can be in the form of a detailed document, implementation, or a proof that such a language exists.

You should reveal the first two languages, but keep the solution language secret.

The cop whose submission takes the longest to crack is the winner.


(robbers' part)

As a robber, you must:

  • Find an existing cop submission.
  • Define a new language which is a superset of both of the languages provided by the cop. This can be in the form of a detailed description, an implementation, or a proof that such a language exists.

The robber who cracks the most cop submissions is the winner.

\$\endgroup\$
  • \$\begingroup\$ So it's a partial mapping? \$\endgroup\$ – user202729 Apr 22 '18 at 14:00
  • \$\begingroup\$ @user202729 Yes \$\endgroup\$ – Esolanging Fruit Apr 22 '18 at 22:36
  • \$\begingroup\$ I don't think that polyglot makes sense here. \$\endgroup\$ – Nissa Apr 23 '18 at 14:16
  • \$\begingroup\$ I don't think this really makes sense as a c'n'r. Both cops and robbers are trying to do the same thing, which is to prove that every program which is valid in both languages gives the same output in those languages. The robber doesn't have to outwit the cop by beating a score or working within extra constraints which the cop chooses and can try to use to add false clues. The only real asymmetry is that the cop chooses the languages, and the only way to exploit that to make it interesting is to make one of them a homebrew which is "specified" with an obfuscated implementation. \$\endgroup\$ – Peter Taylor Apr 25 '18 at 10:56
1
\$\begingroup\$

Decode my Alphabet Code (Cops)

This is my first C&R challenge, so I thought I'd better post it in the sandbox. This is only the Cops thread and it's still missing some usual C&R rules (such as explaining what should be done once a submission has been cracked).


This is the Cops' thread of a challenge. [Link to the Robbers' thread goes here.]

Your task

As a Cop, you must write either a full program or a function that meets the following requirements.

Input

A non-empty string made of at most 26 distinct characters in a given code page. The input is guaranteed to be valid.

The code page is either UTF-8 or -- at your option and if applicable -- a specific code page used by your language.

Output

A string of the same length and in the same code page where the first encountered character is replaced with A, the second encountered character (distinct from the first one) is replaced with B, and so on.

For instance, the expected output for Hello, World! is ABCCDEFGDHCIJ, where A=H, B=e, C=l, etc.

Code restriction

Your code must be a valid input for itself. In other words, it must consist of at most 26 distinct characters in the chosen code page. (But of course, each distinct character may be used several times.)

Your submission

Your submission must contain:

  • The language used
  • The code page used
  • The size of the code in this code page
  • A brief description explaining the nature of your code (program or function) and the I/O formats it's using, in case it slightly differs from string/string.
  • The output produced by applying the transformation to your code

Example:

# MyLanguage, 32 characters in MyLanguage code page

A function taking an array of characters and returning a string.

ABCADAEFGHIEJKDKLMEBCLNEOPPJLNEO

Robbers' task

Robbers must crack your submission by finding a working program that produces exactly the same output once transformed. (Finding a shorter program is not a valid crack.)

Rules

If your answer remains uncracked for a week, you can mark it as Safe and unveil the original code.

The winner is the shortest uncracked answer. In the case of a tie, the oldest answer wins.


Sandbox questions

  • Is it a dupe or too close to an existing challenge?
  • In the original version, the encoding was forced to UTF-8. I'm still not sure which option is the best, so I'm interested in any feedback about that.

  • All other comments and suggestions are much welcomed!

\$\endgroup\$
  • \$\begingroup\$ Do spaces count too ? \$\endgroup\$ – Muhammad Salman Apr 24 '18 at 14:16
  • \$\begingroup\$ @MuhammadSalman Yes, all distinct characters are taken into account. (The space becomes F in my Hello, World! example.) \$\endgroup\$ – Arnauld Apr 24 '18 at 14:18
  • \$\begingroup\$ I suggest only using bytes. Most languages I know of have SBCS anyway, otherwise the translation from UTF8 to bytes are straightforward enough. \$\endgroup\$ – user202729 Apr 24 '18 at 14:20
  • \$\begingroup\$ To be clear, this is not code-golf, correct? \$\endgroup\$ – user202729 Apr 24 '18 at 14:24
  • \$\begingroup\$ @user202729 Using only bytes is indeed another possibility. But it may make the submissions quite harder to check. For instance, if you pass the posted UTF-8 representation of a Jelly program to this same Jelly program which is expecting it in its own code page instead, it's likely to fail. \$\endgroup\$ – Arnauld Apr 24 '18 at 14:34
  • \$\begingroup\$ @user202729 I need to add that the shortest uncracked answer wins. So, I suppose it should be tagged as code-golf as well? (Although the primary winning criterion is to remain uncracked.) \$\endgroup\$ – Arnauld Apr 24 '18 at 14:35
  • \$\begingroup\$ If a language only uses less than 26 characters, can we only support up to that many letters of the alphabet? \$\endgroup\$ – Jo King Apr 25 '18 at 10:30
  • 2
    \$\begingroup\$ @JoKing No, the program must support all inputs. (But of course it's fine if the code itself is only using a couple of distinct letters.) \$\endgroup\$ – Arnauld Apr 25 '18 at 10:37
1
\$\begingroup\$

Clebsch-Gordon coefficients

Clebsch-Gordon coefficients are numbers that arise when adding two quantum mechanical angular momenta. Angular momentum is a vector in three-space and can be described by two numbers j and m. The magnitude of the momentum can be determined by j and its z-component can be determined by m (more on this below).

For quantum mechanical particles, j can only take on nonnegative integer or positive half integer values (0, 1/2, 1, 3/2, 2...). Additionally, its z-component m can only take on values between j and -j inclusive in integer steps. For example if j=1, m can hold values -1, 0 or 1. If j=3/2, m can have values -3/2, -1/2, 1/2 or 3/2.

If an angular momentum has magnitude j and z component m we say it is in the state |j,m⟩. The state can be thought of as a column vector in an infinite dimensional vector space (Hilbert space). It is infinite because there is no upper bound for the value j can take on. From now on when I refer to an angular momentum I will just use it's state to reference it.

j2 and jz operators

I have picked the states |j,m⟩ such that they are eigenvectors of the operators j2 and jz. These operators can be thought of as matrices in the infinite dimensional vector space. Eigenvectors of j2 have eigenvalue equal to a states total angular momentum squared. The eigenvalue of a state operated on by jz is the state's z-component of its angular momentum. The eigenvalues for a state |j,m⟩ are shown below.

j2|j,m⟩=j(j+1)|j,m

jz|j,m⟩=m|j,m⟩.

In words, the square of the magnitude of the angular momentum of state |j,m⟩ is j(j+1) and the z-component of the angular momentum of this state is simply m.

Side notes which do not affect the challenge and you can choose to ignore:

  • We could have just as easily chosen x or y instead of z but the ji operators do not commute so we must decide on one only to create our basis vectors. All ji commute with j2.
  • I have set ħ=1.

Now let's say we have a composite angular momentum with total angular momentum J and z-component M made up of two individual angular momenta. As you might have guessed, this is the state |J,M⟩. We can make equivalent operators J2= and Jz. In order for |J,M⟩ to be an eigenvector of both of these operators is equal to a linear combination of outer products between states |j1,m1⟩ and |j2,m2⟩.

If the angular momenta that compose |J,M⟩ are in states |j1,m1⟩ and |j1,m1⟩...

Clebsch-Gordon explicit formula

Image from wikipedia.

Sandbox

This is an early stage of writing the challenge, but feedback is welcome. If you are familiar with Clebsch-Gordon coefficients I would appreciate any input. They are important in group theory but I am less familiar with that side of them, so if you have a good way of explaining them in that context that would be helpful.

I plan on asking for the square of the coefficients so as not to worry about floating point numbers.

  • Should I require sign of the coefficients as well or just magnitude?
\$\endgroup\$
  • \$\begingroup\$ Might be useful: Mathematica's built-in ClebschGordan, which you can test on the open sandbox. \$\endgroup\$ – lastresort Apr 19 '18 at 9:06
  • 1
    \$\begingroup\$ It's not clear to me what the inputs are, and therefore what the outputs are. It's also not clear what the range of the sum is: the entire support? \$\endgroup\$ – Peter Taylor Apr 19 '18 at 10:05
  • \$\begingroup\$ @petertaylor yes, thanks I still need to addbthatvinfo \$\endgroup\$ – dylnan Apr 19 '18 at 12:55
  • \$\begingroup\$ @lastresort thanks! I did see there was a built in :) \$\endgroup\$ – dylnan Apr 19 '18 at 12:56
  • \$\begingroup\$ What's the challenge here? \$\endgroup\$ – LastStar007 Apr 27 '18 at 9:24
1
\$\begingroup\$

Integers as "polynomials"

Suppose we use successive digits of an non-negative integer for coefficient, base and power respectively and construct a "polynomial". For a 4-digit number we'll have:

abcd -> a*b^c + b*c^d + c*d^a + d*a^c.

Each digit must go through the three roles exactly once. For the last two members we wrap around the right edge and use the first/second digit again.

For example 1234 will represent the following "polynomial":

1*2^3 + 2*3^4 + 3*4^1 + 4*1^2 -> 1*8 + 2*81 + 3*4 +4*1 -> 186

We started with an integer and ended with an integer. That gives me the idea that we can feed the result into the procedure again and keep calculating. As it seems the numbers will sooner or later start repeating, leading to an endless loop. For example:

4 -> 1024 -> 12 -> 4 -> ...

I'm interested in how many cycles are needed until we come to a number that has already been calulated.

The Task:

Start with a non-negative integer and calculate my "polynomial" from it. Keep calculating using the result as input until you reach a number that has already been calculated.

Your answer must be theoretically correct if your language's integer types had infinite width, but you may use any integer type with at least 8 bits

Input:

You can take the input as:

  • A non-negative integer
  • A list of digits
  • A string

Output:

A single integer - the number of cycles until a known number is reached.

Winning criteria:

This is , so shortest code in bytes in each language wins. Explanations of the code are welcome!

Test cases:

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

\$\endgroup\$
  • \$\begingroup\$ "Not surprisingly the numbers will sooner or later start repeating, leading to an endless loop" Do you have a proof of this? It seems plausible but not obvious that no chain escapes to infinity. \$\endgroup\$ – Peter Taylor Apr 30 '18 at 14:59
  • \$\begingroup\$ @Peter Taylor - No, I don't have any proof. Maybe I need to change the description? \$\endgroup\$ – Galen Ivanov Apr 30 '18 at 15:18
  • 1
    \$\begingroup\$ I've found a proof: 12 x 9<sup>10</sup> = 4.1841412812 x 10<sup>10</sup>, so any number with 12 or more digits maps to a number with fewer digits. There is one thing which I think it's probably worth adding, and that's a statement about overflow. Options include "Your answer must be correct if intermediate values don't exceed N bits, but may be incorrect if they do exceed that"; "Your answer must be theoretically correct if your language's integer types had infinite width, but you may use any integer type with at least 8 bits". \$\endgroup\$ – Peter Taylor Apr 30 '18 at 15:41
  • \$\begingroup\$ @ Peter Taylor Thank you for your help! You are completely right abiut the overflow - I have used J's extended precision to make the test cases. I'm going to update the description. \$\endgroup\$ – Galen Ivanov May 1 '18 at 8:35
1
\$\begingroup\$

Relational Division

Given a database of colored marbles in bins, find which bin has the most marbles of a certain color. In database administration, this task is known as relational division.

Example

Input marbles (flexible format, this is just one possibility):

red,A
blue,B
green,C
red,B
red,A
blue,A

Input color:

red

Program output:

A

Format

Each 'marble' is represented as a (color, bin) pair, so the entire database of marbles is represented by a list of these pairs. The list can be fed into your program in any reasonable way so long as the association of the input data remains between colors and bins -- for example via CSV on stdin in color,bin pairs split on newlines in string-manipulation programs, or perhaps via a list of (str, str) tuples as a parameter to a function in a language like Python. It's up to you.

In my examples, I'm using strings to represent colors and bins, but you can use any data type that is capable of representing at least 1000 distinct values in your programming language (i.e. no booleans). Examples of other acceptable data types would be integers or floats so long as you're consistent.

It's very important that colors cannot be used as bins, and bins cannot be used as colors (i.e. the set of bin identifiers and the set of color identifiers must be disjoint). If this isn't true, the result is undefined.

In addition to the marble database, your program takes in a color identifier, again in whatever way is most convenient to do I/O of a single value in your language. Your program must output or return a unique identifier for the bin that contains the most marbles of that color.

The result is undefined if the input color doesn't exist, or if there is a tie between multiple bins (i.e. if the input color is red, there are 70 red marbles in total, and two bins both have 30 red marbles). Your program should be expected to handle up to 1000 input marbles without much difficulty.

This is a challenge, so the shortest program wins, with submission time (earlier is better) as the tiebreaker.

\$\endgroup\$
  • 2
    \$\begingroup\$ If it's a function, it must output to stdout too? Huh? \$\endgroup\$ – user202729 May 3 '18 at 1:28
  • \$\begingroup\$ @user202729 Thanks, bug fixed! \$\endgroup\$ – Harry May 3 '18 at 3:10
1
\$\begingroup\$

Conway's Battlegrounds


Conway's Battlegrounds will be a mix of PUBG and Conway's Game of Life. In this challenge, you will need to make a Python bot that will play it.

Game rules

The controller, at the beginning of the round, will create a two-dimensional 500x500 toroidal (edge wrapping) board with chosen cells being alive, the others are dead.

The players are then separated into equal teams, each with 4 bots. If there isn't enough players in the team, some of them might be duplicated.

Gameplay

"Parachuting" phase

Everybody in the game will be given the array representing the starting state of the board. Each bot's class will be initialized, with these arguments in order:

  • num - an int between 2 and 5 inclusive, representing the number you'd be marked with on the map during the game. The other numbers in the range will be your party members.
  • area - Dictionary, where each key is a 2 value tuple (x,y) and each value is either a 0 (dead cell) or 1 (alive cell)

During this phase, each bot's method parachute will be called exactly 10 times. It will be given only one argument:

  • team - 4 item dictionary with your and each teammate's ID (between 2 and 5) as key and a 2 item tuple as value, representing the (x,y) position they chosen, or None if they didn't yet chose any.

The method can return a 2 value tuple, representing where the bot want to start or None, if the bot can't decide. The returned value will be visible to every other teammate.

The method will be called again, even if the player already chose a location. The next return value will replace previous. You can prevent that by returning team[self.num], assuming you saved the num parameter from __init__.

It is recommended to spawn your bot near teammates, so it's easier to cooperate later.

If the method has been called the 10th time and the bot didn't return that time a (int, int) tuple, it will be removed from the game.

Each bot will then be spawned at a random location in a 9x9 rectangle, with the returned location in the center. The bot will not collide with other players.

Starting phase

This phase will take exactly 25 turns. It's almost the same as the later, main phase of the game, except that no cell will die or be created in it.

The start method of each bot will be called once every turn. It will take these arguments in order:

  • area - Basically the same as in the previous phase, but with several modifications:
    • It will be only a 25x25 fragment of the map, with the bot in the middle.
    • It might also contain the ints in range 2..5 representing each teammate.
    • It might also contain the int -1 representing an opponent.
  • turn - The number of the turn, starting with 0. In the last turn of the phase it will be 24.
  • chat - a list of new chat messages, stored in tuples (author_id, msg_id)

The method must return a 0..4 value tuple or list, which may contain up to three actions the bot will perform during it and optionally a single chat message. Each item in tuple is a one move, depending on the value:

  • Falsy values (0, None, False) - Do nothing
  • Positive int - Move in given direction, according to the rule (where the bot is in the center):

    1 2 3
    4   6
    7 8 9
    

    Bot can only move to a neutral position.

  • Negative int - Replace a neighbour dead cell with a neutral alive cell, according to the rule above, ex. -1.
  • String - Send a chat message with the given ID, explained later

Main phase

Similar to the previous phase, but in this one, cells can die. It won't end until only one team is on the board.

The main method of each bot will be called once every turn. It will take these arguments in order:

  • area - Same as in starting phase
  • team - Dictionary with position of teammates id: (x, y)
  • turn - The number of the turn, starting with 0. In the last turn of the phase it will be 24.
  • hp - The amount of health points the bot has, explained later. Initially 4.
  • chat - a list of new chat messages, stored in tuples (author_id, msg_id)

The return value is the same as in the previous phase.

Neighbours, dying and reproducing

  • A neighbour of a cell a is an another cell that is positioned next to the cell a, either orthogonal or diagonal.
  • A neutral cell is any cell that is either 0 or 1 (isn't a bot).
  • A bot cell is any cell occupied by a bot, that is, the negative number -1 and positive 2, 3, 4, 5.
  • A dead cell is any cell that is exactly 0.
  • An alive cell is any cell that is not dead (0). This includes both bot cells and 1's.

In this round, cells can die. They can also reproduce.

  • Neutral cells (marked 1) will die (turn to 0) if amount of their alive neighbours is not 2 nor 3.
  • Dead cells (marked 0) will reproduce (turn to 1) if amount of their alive neighbours is exactly 3.

Rules about bot cells (-1 and greater than 1) are a bit different though.

  • Bot cells will lose 1 hp if amount of their alive neighbours is not 2 nor 3 and no natural cells were reproduced in the neighbourhood.
  • Bot cells will die if they have 0 hp.
  • Bot cells will gain 1 hp if amount of their alive neighbours is equal to 3 and at least 1 neighbour is a teammate. Cell will not gain hp if it has 3 or more hp.
  • Bot cells will be moved if amount of their alive neighbours is not 2 nor 3 and a single nearby cell was reproduced (it will replace it). Bot cells cannot duplicate.

The red zone

Every 100 generations (turns), the red zone will start in the place with most dead cells. It will end after 10 turns, and every second turn it will spawn a glider.

Chatting

Bots in the same team can communicate between themselves during the game.

Some of the messages were made because of how the board is generated. Make sure you read this before, so you can use it to collaborate with other bots easier.

Here's a list of all "built-in" messages:

  • 1 - Help!
  • 2 - Wait!
  • 3 - Need healing!
  • 4 - Come here
  • 5 - Enemies are nearby
  • 6 - I'll fight
  • 7 - I'll build
  • 8 - Search for boats/Build a boat
  • 9 - Get in the boat
  • 10 - Exit the glider

The controller

WIP, I won't probably have time to make it this week.

Example bot

A classic random bot, won't survive long.

import random


class RandomBot:

    def __init__(*args): pass

    def parachute(self, team: dict):

        return random.choice([x for x in team.values() if x])

    def start(*args):

        return random.randint(-9, 9)

    def main(*args):

        return RandomBot.start()

Additional rules

  • You have access only to non-superuser built-in Python packages
  • You must not create, write nor open any files
  • You cannot access any of internal or other bot's classes
  • You cannot modify any mutable arguments given to your methods, only their copies
  • You shouldn't throw any exceptions
  • You must return only specified values.
  • The code you publish here must not output anything
\$\endgroup\$
  • \$\begingroup\$ During the parachute phase, the team[self.id] should be that bot's last return value, and the other values should be the other teammates in the same order as their ids. \$\endgroup\$ – SIGSTACKFAULT May 7 '18 at 18:28
  • \$\begingroup\$ You say that bots are given Ids from 2 to 6 inclusive with a team of size 4. However, there are 5 values in the range 2 to 6 inclusive. \$\endgroup\$ – Kamil Drakari May 7 '18 at 18:46
  • \$\begingroup\$ @KamilDrakari I noticed that earlier, but somehow didn't edit it in. Thank you! \$\endgroup\$ – RedClover May 7 '18 at 19:05
  • 1
    \$\begingroup\$ I think it needs to be made clearer that the Game Of Life part of this challenge essentially treats all bot locations as "alive" cells. So the location of a bot is relevant for cells spontaneously becoming alive, the bot loses HP in situations where a cell would die, etc. That was the impression that I got, but it didn't immediately "click". Moving the bot if an adjacent tile reproduces and the bot would otherwise take damage is unintuitive, but I guess there's probably a good reason for it. \$\endgroup\$ – Kamil Drakari May 7 '18 at 19:23
  • \$\begingroup\$ @KamilDrakari I edited the challenge to make it more clear. Originally, the reason for bots moving instead of taking damage was to allow the existence of vehicles, but as I look on the challenge now, I think I screwed it up, because a vehicle (glider) won't be any faster than the cell itself. Unless I increase amount of generation between turns \$\endgroup\$ – RedClover May 8 '18 at 11:34
  • \$\begingroup\$ @Soaku I don't think having multiple generations between turns sounds fun, and it adds some extra weirdness to taking damage (either you can take damage multiple times with no way to act, or you lose the "take damage any time your cell would die" symmetry). I think losing the vehicles is a better tradeoff. \$\endgroup\$ – Kamil Drakari May 8 '18 at 12:37
  • \$\begingroup\$ @KamilDrakari I know. So given that, the rule doesn't make any sense now. \$\endgroup\$ – RedClover May 8 '18 at 12:48
1
\$\begingroup\$

Nice Tile Connector

Your task is to connect the tiles given to you in the input by removing the lines on sides they connect

Input

A set of tiles that are not yet connected

Output

The tiles with the walls removed in the right places to connect them

Method

Each tile in the input looks like this:

___
|~|
|_|

Every air space looks like this:

...
...
...

On a tile, the top line is in front of the side lines, which are both in front of the bottom line. That means the top line will always replace the | characters that would be there on the sides, and the side lines will always replace the _ characters that would be there on the bottom.

Each tile must have any lines removed that are adjacent to other tiles

Example

The input

...______...
...|~||~|...
...|_||_|...
...___...___
...|~|...|~|
...|_|...|_|
...______...
...|~||~|...
...|_||_|...

The output

...______...
...|~~~~|...
...|~~__|...
...|~|...___
...|~|...|~|
...|~|...|_|
...|~~___...
...|~~~~|...
...|~~~~|...

As this is , smallest solution in bytes wins.

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

Pascal Squared Sums

Most everyone here is familiar with Pascal's triangle, which is formed by taking the summation of the two parent objects. Here are the first few rows:

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1
    ...

Let's instead rotate this to the left by 45 degrees, and assume that it's forming an infinite matrix. Alternatively, this can be thought of as the triangle is reading the anti-diagonals of the matrix.

1 1 1 1 1
1 2 3 4
1 3 6
1 4   ...
1

Given an input n, take the top-left n x n sub-matrix of this infinite matrix. Then, take the column sums of that n x n matrix as your output.

For example, for input n = 3, this would result in the sub-matrix

1 1 1
1 2 3
1 3 6

Taking the column sums gives us 3, 6, 10, so our output is [3, 6, 10].

Standard I/O Boilerplate

\$\endgroup\$
  • \$\begingroup\$ Note that the output are just the [2~k+1]'th element on the k'th row (1-indexing) \$\endgroup\$ – user202729 May 11 '18 at 16:27
  • \$\begingroup\$ @user202729 Really? Dang. I was hoping there was a nice relation, but I didn't expect something that simple. Hmm, maybe need to rethink this. \$\endgroup\$ – AdmBorkBork May 11 '18 at 16:54
  • \$\begingroup\$ Neim, 6 bytes: p₁ᛖ𝕖2𝕘 (polygonal list with side length of input, select first double input elements, remove first two elements) \$\endgroup\$ – Okx May 11 '18 at 20:36
1
\$\begingroup\$

Polyraptor/Forerunner Combo

Notice: You probably need to understand the Stack in MTG for this challenge!

A new expansion to the trading card game Magic: The Gathering, Rivals of Ixalan, was released this January. In this set were the two cards important to this challenge: Forerunner of the Empire and Polyraptor, as I learned just now after losing a game of MTG Arena.

Forerunner of the Empire Polyraptor

I like the Polyraptor in the background of Forerunner. Wizards knew precisely what they had brought about.

If you'll notice, if a Polyraptor enters the battlefield under your control, since it's a Dinosaur (look at the bit just below the art), it triggers Forerunner of the Empire's second ability. You may then have the Forerunner deal one damage to all creatures, including itself and Polyraptor! This clones Polyraptor, and the clone ALSO TRIGGERS THE ABILITY! This time, each Polyraptor (there are two now) takes one damage, and TWO new clones spring into being! However, these clone-making abilities execute one after another, not simultaneously. Both are pushed to the Stack, and the second pops and resolves. The Polyraptor clone enters the battlefield and triggers the Forerunner's ability BEFORE the second Polyraptor clone is created (Forerunner's ability pops from the Stack earlier). Again, Forerunner of the Empire deals one damage to each creature. There are now three Polyraptors, and each takes one damage. Three more Polyraptor clonings enter the Stack, which now contains four. The Forerunner, having at this point taken three damage this turn, dies, and the rest of the Polyraptors enter the battlefield without triggering its ability. When all's said and done, there are seven Polyraptors on the battlefield.

Generalization

Now, imagine for a moment that Forerunner had five toughness and Polyraptor three instead. Let PA := Polyraptor-cloning ability and FA := One damage to all creatures.

Polyraptor enters.                        Stack: FA
Forerunner deals one to each creature.    Stack: PA PA
Polyraptor enters.                        Stack: PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA
Polyraptor enters.                        Stack: PA PA PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA PA PA
  At this point, the original Polyraptor dies. It will no longer take damage. Three left.
Polyraptor enters.                        Stack: PA PA PA PA PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA PA PA PA PA
  Another Polyraptor dies. Three left.
Polyraptor enters.                        Stack: PA PA PA PA PA PA PA FA
Forerunner deals one to each creature.    Stack: PA PA PA PA PA PA PA PA PA PA
  Another Polyraptor dies. Three left.
  Forerunner also dies here.
The Stack empties with no more abilies triggered.

Here, the final Polyraptor count is 13.

Your task

Write a program or function that takes as input two nonnegative integers F and P and returns the final count of Polyraptors when a Polyraptor with toughness P is cast while its owner controls a Forerunner of the Empire with toughness F.

Test cases

Form: F, followed by P, followed by the result and an explanation.

0 0
0
The Forerunner has zero toughness, so it dies before anything happens. The Polyraptor dies immediately upon entering play.

0 5
1
As before, the Forerunner dies, but this time, the Polyraptor lives to see the dawn.

1 0
0
The Forerunner's ability triggers once, but all Polyraptors die on their own.

1 5
2
This time, the Forerunner kills itself damaging and copying the Polyraptor once.

2 5
4
Again, Forerunner kills itself, but this time, it manages to copy the Polyraptor and then both the original and the copy.

3 5
7
See above

5 3
13
See above

More coming! This is hard to do by hand :|

Rules

  • Forerunner of the Empire's ability says "may". Ignore that—it always deals the damage.
  • Standard loopholes are forbidden.
  • I/O is flexible.
  • This is , so the shortest solution (in bytes) in each language wins! Happy golfing!

Sandboxy Stuff

Did I mess up a test case?

What do y'all think? Should I explain the Stack so all can understand?

\$\endgroup\$
  • \$\begingroup\$ I think you did mess up the 5 3 test case: I get 10, and 5 4 gives 13. Reference implementation (goes to tio.run but I had to use a link shortener because of the limitations of comments and because I used ungolfed variable names etc.) \$\endgroup\$ – Peter Taylor May 14 '18 at 10:30
  • 1
    \$\begingroup\$ And on the basis of reference values, I claim that the solution is pretty straightforward by case split: using f and p respectively for Forerunner and Polyraptor toughness, it's p == 0 ? 0 : f < p ? f*(f+1)/2+1 : p*(p+1)/2 + (f-p)*(p-1), where the last case can be golfed to p*(3-p)/2+f*(p-1). Not sure there's enough here for an interesting challenge. \$\endgroup\$ – Peter Taylor May 14 '18 at 10:44
1
\$\begingroup\$

Create a solver for the Topspin puzzle

The Topspin puzzle consists of 20 round pieces in one long looped track. The pieces can slide along the loop. There is a turntable on one of the sides of the the loop which can rotate the four adjacent pieces laying within it, so that they reverse their order.

By sliding the pieces left and right and rotating the turntable the puzzle can be scrambled.

The goal is to restore the pieces in their initital order by sliding / rotating them.

Topspin

You can learn more about the puzzle here: https://www.jaapsch.net/puzzles/topspin.htm

Task:

Write a program / function that solves the Topspin puzzle from a scrambled to ordered state.

Input:

The input is a list of the numbered scrambled pieces, in any convenient format. For example:

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

You can use 0-indexing, just mention it.

Output:

The output is a list of moves that solve the puzzle. You a free to chose a notation which suits your language / algorithm. Possible notation:

  • 0 - rotate the turntable
  • 1 - slide all pieces to the left
  • 2 - slide all pieces to the right

or:

  • t - rotate the turntable
  • l - slide all pieces to the left
  • r - slide all pieces to the right

Since the pieces form a loop it is NOT necessary to shift the pieces in the final solution so that the lists starts at 1.

So the output should look something like this:

011022201... and so on

or

tllltltrrt...

Test cases:

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

You can use this script to generate more scrambled sequences: Try it online!

You can check your solution with this script: Try it online!

(a is 1-indexed list of the scrambled pieces, b is the solution in notation - 1 - slide to left, 2 - slide to right, 3 - turn )

Winning criteria:

This is , so the shorest solutions in bytes in each language win. Please explain you algorithm!

\$\endgroup\$
  • 2
    \$\begingroup\$ Unless I'm missing something, there's no requirement that the solution be the shortest possible, so two moves are sufficient, and it will probably give shorter code to only use two. There's also no requirement that the program finish in any finite limit. Are both of these intentional? \$\endgroup\$ – Peter Taylor May 14 '18 at 14:53
  • \$\begingroup\$ @Peter Taylor Thank you for your feedback! No, they are not intentional, but my omission. In fact I was wondering how to add the length of the solution (multiplied by some coefficient < 1) to the length of the code and make the total score. I'm open for any suggestions. \$\endgroup\$ – Galen Ivanov May 14 '18 at 18:00
  • \$\begingroup\$ can the output notation be code? \$\endgroup\$ – l4m2 May 15 '18 at 9:29
  • \$\begingroup\$ @l4m2 I'm not sure what you mean. Can you show/explain? \$\endgroup\$ – Galen Ivanov May 15 '18 at 10:09
  • 1
    \$\begingroup\$ Combining two elements to give a single score is usually tricky. GAP finds a solution for 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 of length 183, so bubble sort should be able to solve an arbitrary permutation in (modulo out-by-one errors) at most 19*10+19*18/2*183 = 31483 moves. Might be worth downloading GAP and seeing what it finds for random permutations, or even whether GrowthFunctionOfGroup completes in a reasonable time. \$\endgroup\$ – Peter Taylor May 16 '18 at 11:39
  • \$\begingroup\$ @Peter Taylor Thanks! I don't have any experience with GAP, although I have it installed on my computer. I'll give it a try. \$\endgroup\$ – Galen Ivanov May 16 '18 at 13:17
  • \$\begingroup\$ I would just try a bozo sort (and hope it works) if this question does not include the requirements of size of the solution... \$\endgroup\$ – tsh May 18 '18 at 8:10
  • \$\begingroup\$ @tsh This is exactly how most people try to solve puzzles :) I think I need to add a requirement that the solution should be reachable in reasonable time. \$\endgroup\$ – Galen Ivanov May 18 '18 at 8:29
1
\$\begingroup\$

The following is an idea I hope to eventually make into a full king of the hill. I've never written or participated in a king of the hill so help would be appreciated.

Here is how this is going to work. You are going to be able to write the brain behind a bot. Your bot will have a limited amount of energy to work with. It won't have to expend energy to move around normally, however every time it moves while carrying something it will expend 1 unit of energy. When your bot hits zero energy it won't be able to move any longer and will die have to take a nap.

The goal is to make bots that will take agar from sources to their corresponding goals. However the sources and goals will be too far apart for a single bot to carry a piece of agar all by themselves so you will need to work with other bots to achieve your goals.

Specifics

The course

The course will likely be a square grid of yet determined size. On the south and east ends will be sources of agar, which will replenish as it is drained by the bots. On the north and west ends will be goals. Agar placed in the goal will disappear. Agar from the east source should be placed in the west goal and agar from the south source in the north goal.

The bots

Each player will be given control of 1 bot. Bots will be implemented as a rather simple state-machine. You will implement your bot as a function that takes inputs and produces outputs. At each step of the program a the bot will receive the following pieces of information:

  • Whether each of the four squares adjacent to it is inside our outside of the arena.

  • Whether there is agar in each of the four squares adjacent to it, and the square it is in.

  • Whether there is another bot in each of the four squares adjacent to it.

  • Whether it is carrying agar currently.

  • How much energy it has remaining.

  • An additional 2 bit state, to be explained.

From those inputs the bot will produce two outputs:

  • An action, which is either a direction to move, picking up agar, or placing agar back on the ground.

  • A 2 bit state to be passed on to your bot at the next step.

The 2 bit state acts as your bot's memory. It's not a lot so you should use it wisely.

Movement

Your bot has pretty free movement. It can move into any empty space. However there are two limits on movement.

  • You may not move outside of the course

  • You may not move into a space that has agar if you are carrying agar.

I am not yet sure how I will handle bot collisions.

Carrying

Your bots can carry agar. They can only carry one piece of agar at a time. To pick up agar a bot must be standing where the agar is located and perform a pick up action. Placing agar works in much the same way. If a bot is carrying agar they may perform a place action to put the agar down where they stand. Placed agar will remain there until a bot picks it up and moves it. Picking up and placing agar does not cost energy, however moving while holding agar does cost a unit of energy for every movement.

Scoring

Scoring is still up in the air, once I have a working controller I will finalize scoring aspects. That being said thoughts, questions and suggestions are more than welcome.

Each piece of agar will remember which bots helped move it and how many steps they took. Upon being put into the correct goal agar will award every bot 1 point for every step they took while holding the agar. Agar left on the field or put in an incorrect goal will award no points.

More points is better.

I'm not sure how koth scoring usually works overall so you guys might want to help me with that.

Controller

Once I have the idea down I will start to write a controller. I may need some help from people more experienced in koths in getting the basics down.

I intend to write the controller in elm because I like functional programming and I would like the controller to be runnable from in browser. Answerers will not have to write in elm they will instead write in a toy language I have yet to write the specifics for.

\$\endgroup\$
  • \$\begingroup\$ A few points, all related to a particular event/strategy: 1) Do bots pick up/put down agar in any adjacent square, or specifically on their current square? 2) If a bot picks up then puts down agar without moving in between, does that use energy? 3) Mostly dependent on 1, but if a bot picks up agar and puts it down somewhere else, does that count for scoring even if the bot itself didn't move in between? \$\endgroup\$ – Kamil Drakari Apr 20 '18 at 18:59
  • \$\begingroup\$ @KamilDrakari Bots must stand on agar to pick it up, and placed agar will appear where they stand when they place it. \$\endgroup\$ – Sriotchilism O'Zaic Apr 20 '18 at 19:00
  • \$\begingroup\$ Since you're passing the state with every function call anyways, you could also run each bot as a single process which would allow people to participate in any language of their choice. I once planned a KOTH (which has some copyright issues and I can't post it) and wrote a Python framework, if you're interested I'd share it. Basically it creates a new process for each bot and controller-bot communication works via pipes, st. the bot can just read stdin and write to stdout. This would probably attract more participants than forcing a language. \$\endgroup\$ – ბიმო Apr 21 '18 at 12:32
  • \$\begingroup\$ @BMO The main reason I am using purescript is that it is runnable in browser. I could definitely make this language agnostic but I would have to make it into a desktop application. I'd greatly prefer a challenge that can be run in browser. In addition purescript's pattern matching makes it so you don't really have to know purescript to write a working bot. I can easily write a form that can be filled out to make a bot. \$\endgroup\$ – Sriotchilism O'Zaic Apr 21 '18 at 14:58
  • \$\begingroup\$ Ah, yes that makes sense that people are able to run it in a browser. I've never used purescript but it seems like a nice language. I'm not sure though if people would be willing to get involved with it (not everyone is comfortable with strong type systems), however it seems like there are a lot of people that know JavaScript. So it's probably a good choice for a KOTH. \$\endgroup\$ – ბიმო Apr 21 '18 at 15:31
1
\$\begingroup\$

What a hat at wheat!

Given a word, remove letters one at a time until nothing is left. Output the list of steps.

Example:

 wheat
 what or heat
 hat or eat
 at or ha
 a

All words must exist in a word list, but this list may be provided via any means, such as in a file with a specific name, or in a global variable, or built-in to the language, as long as it's a list of words and not some custom data structure. You can however require that the list is pre-sorted in a specific order (in which case you should also provide a suitable sort function, which can be in any language).

If there is more than one solution then you can return any one or all solutions. If there are no solutions then you should return a falsy value. You can assume that the input is taken from the word list. You don't need to return the original input or the empty string as part of the solution.

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Heavily-downvoted dupe. \$\endgroup\$ – Erik the Outgolfer May 24 '18 at 9:16
  • \$\begingroup\$ Technically the other one is not a duplicate target because a <Jelly> solution for this one can't be "easily" ported there... \$\endgroup\$ – user202729 May 24 '18 at 9:17
  • \$\begingroup\$ @user202729 Yeah, the reason it's heavily downvoted is that it restricts to 4 languages. \$\endgroup\$ – Erik the Outgolfer May 24 '18 at 9:21
  • \$\begingroup\$ I'd like the word list to be provided as an argument. Otherwise this is a good challenge, and a good dupe target to close the other one. \$\endgroup\$ – lirtosiast Feb 2 at 1:40
1
\$\begingroup\$

Softcode, take 2

Softcoding is an anti-pattern defined by “the practice of removing ‘things that should be in source code’ from source code and placing them in some external resource”, which usually are config files, database entries, or both. “At the extreme end, soft-coded programs develop their own poorly designed and implemented scripting languages”, as can be seen by one of the most egregious examples of the practice, the Enterprise Rules Engine.

Thus, programmers who fall to the habit of softcoding, after tons of work, find themselves at the very point they were starting from: they have developed “some sort of COmmon Business-Oriented Language that’s generic enough to code any rule”. But unfortunately for them, there already is such a thing. “It’s called C++. And Java. And C#. And Basic. And, dare I say, COBOL.

For the sources of the above quotations are more information of the practise, see: Soft Coding on The Daily WTF, Softcoding on Wikipedia and The Enterprise Rules Engine on The Daily WTF.

The Challenge

Softcode! Make an actual, Turing-complete language that will reside in config files!

More specifically, you should write a compiler / interpreter / anything in between that will define a Turing-complete programming language, whose every valid source code will also be a valid JSON file. (The reason why JSON has been chosen is the simplicity of syntax and wide avalability of JSON parsers, so that you won't have to write a parser yourself.)

Input/output format of your JSON language is up to you.

Shortest interpreter / compiler code wins, as long as it implements a Turing-complete language.

Technical details

Unfortunately, given how this challenge is defined, I must put one arbitrary restriction: If your language of choice supports calling a compiler or interpreter of any Turing-complete language, I must disallow doing that. Otherwise, this challenge would likely degrade to calling eval on a single property name of your JSON input file.

However, not to burden you with writing JSON parsers, you may use third-party libraries, as long as they're freely available. (Otherwise, good ol' C++ would be a nightmare without Boost.)

Be creative.

Example interpreter

For reference, below is a simple JS interpreter of a Turing-complete JSON programming language. Of course, this code is ungolfed. (I hope there are no bugs in this interpreter, but I don't feel like testing it now.)

importPackage(java.io);
importPackage(java.lang);

// This interpreter implements GOTO-programs, which are Turing-complete.

var stdin = new BufferedReader( new InputStreamReader(System['in']) );
var progsrc = stdin.readLine();
var prog = JSON.parse(progsrc).prog;

var vars = {};
vars.in = Number(stdin.readLine());

for(var i = 0; i < prog.length; i++) {
    switch(prog[i].command) {
        case 'ADD':
            vars[prog[i].varname] = vars[prog[i].varname] || 0;
            vars[prog[i].varname] += prog[i].constant;
            break;
        case 'SUBSTRACT':
            vars[prog[i].varname] = vars[prog[i].varname] || 0;
            vars[prog[i].varname] -= prog[i].constant;
            break;
        case 'GOTO':
            i = prog[i].index-1;
            break;
        case 'IF':
            vars[prog[i].varname] = vars[prog[i].varname] || 0;
            if(vars[prog[i].varname] == prog[i].constant) {
                i = prog[i].index-1;
            }
            break;
        case 'HALT':
            i = prog.length;
            break;
    }
}

vars.out = vars.out || 0;
print(vars.out);
\$\endgroup\$
  • \$\begingroup\$ You realize that allowing eval make the challenge trivial. Good. Now you don't allow eval, we just need to implement it. The challenge degrades to "implement the 'eval' function for any Turing-complete language". Not good at all. \$\endgroup\$ – user202729 May 27 '18 at 10:00
  • \$\begingroup\$ Looks like that it's very difficult for you to write a well-received challenge. It's unfortunate... \$\endgroup\$ – user202729 May 27 '18 at 10:05
  • \$\begingroup\$ @user202729 You May Not Call Any Already-Existant Compiler Nor Interpreter For Any Turing-Complete Language, is this OK? How are you going to "implement eval" with such a requirement? \$\endgroup\$ – gaazkam May 27 '18 at 10:28
  • \$\begingroup\$ Just reimplement it. For some simple language, e.g., BF. \$\endgroup\$ – user202729 May 27 '18 at 11:11
  • \$\begingroup\$ @user202729 How is implementing BF going to be shorter (in bytes) than, say, GOTO-programs, WHILE-programs or lambda calculus? BF has 8 instructions, you can do GOTO with 2 \$\endgroup\$ – gaazkam May 27 '18 at 11:17
  • \$\begingroup\$ @user202729 Besides, writing a BF interpreter is an interesting golfing challenge on its own. Figuring out which language will allow a shortest interpreter just adds more depth. \$\endgroup\$ – gaazkam May 27 '18 at 11:34
  • 1
    \$\begingroup\$ My point is, this challenge degrades to "interpret any TC language", and the "soft code" part doesn't make the problem significantly different. \$\endgroup\$ – user202729 May 27 '18 at 11:53
  • 1
    \$\begingroup\$ And would probably be closed as duplicate of this. \$\endgroup\$ – user202729 May 27 '18 at 13:58
  • \$\begingroup\$ @user202729, or closed as "Too broad", as that question also should be. \$\endgroup\$ – Peter Taylor May 29 '18 at 13:39
1
\$\begingroup\$

Othello Greedy Strategy

The rules for Othello can be found here.

In a greedy strategy, in each go, you just choose a square in which to place your counter such that there are no other places that could allow you to flip more counters. However, there is still often a choice where you need to decide where to put your counter.

Given an integer N as input, when black goes first and both players follow a greedy strategy, output a possible configuration of counters at the end of the game where there are N black counters. Assume that there exists a configuration for N.

Output should be a 64-character string, where the (r-1)*8+1th to r*8th characters (inclusive) represent the rth row from left to right.

I'll add test cases if people think that this is a good challenge.

\$\endgroup\$
  • \$\begingroup\$ I think the core of the challenge is interesting (Implementing Othello rules). However, I think a better way to present it is to give them a board, and have them output a greedy move. \$\endgroup\$ – Nathan Merrill May 31 '18 at 14:33
  • \$\begingroup\$ I think you should add the rules in your post (challenges should be self-contained) \$\endgroup\$ – wastl Jun 1 '18 at 7:30
  • \$\begingroup\$ Although the challenge is interrsting, I have no idea how can I solve this in a teasonable time. NathanMerrill's suggestionis better. \$\endgroup\$ – user202729 Jun 2 '18 at 7:24
1
\$\begingroup\$

Array-of-arrays string conversion

Matrix challenges are popular. There's an issue of how to provide test cases. A common method is the row-wise array-of-arrays representation, such as:

[[1,2],[3,4],[5,6]] -> a 3 by 2 matrix

This is good with vertical space, but there's always the task of converting the test cases into something your language can use, and vice versa for producing test cases to this format.

So this is a challenge and also a repository of conversion functions that people can use when trying or composing matrix challenges.

Defining the format

A row string of length m is a comma-separated list of m ≥ 1 numbers, enclosed in square brackets.

A row-wise n×m array-of-arrays string is a comma-separated list of n ≥ 1 row strings of length m enclosed in square brackets.

There can be no leading whitespace. One trailing newline immediately after the final ] is optional. Otherwise any whitespace in the string is optional.

The challenge

Produce two* programs/functions in your language:

  1. one which takes a rowwise n×m array-of-arrays string as an input, and outputs the matrix (as implemented in the language.)

  2. another one which takes an n×m matrix (as implemented in the language) as an input and outputs the rowwise n×m array-of-arrays string.

*It is allowed for one program/function to perform both tasks and you can have helper code used by both conversion functions.

Rules

  • To be clear: the language must support matrices (or something equivalent like 2D arrays - the name is not important) because the output/input of the two tasks needs to be an actual matrix in the language.
  • This is .
  • Fewest total number of bytes (from all functions and any helper code) in each language wins.
  • If one program or function does both conversions, only count those bytes once.
  • Standard rules apply/loopholes forbidden.

Here's the Sandbox and a related question.

\$\endgroup\$
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – ngm May 30 '18 at 18:54
  • \$\begingroup\$ I'm not sure if I need to explicitly mention the case where the string as defined is already a valid matrix or expression in some language. And if I do need to mention this case, I don't know what the best terminology to use might be. \$\endgroup\$ – ngm May 31 '18 at 15:08
  • \$\begingroup\$ Thank you for all your input. I will leave it in the sandbox for another day or two in case other issues arise. \$\endgroup\$ – ngm May 31 '18 at 16:59
  • \$\begingroup\$ @Adám I've removed "expression" from the question. \$\endgroup\$ – ngm Jun 1 '18 at 13:48
  • \$\begingroup\$ @user202729 I've added the link to the question. \$\endgroup\$ – ngm Jun 1 '18 at 13:48
  • \$\begingroup\$ I think this one is ready to post. \$\endgroup\$ – Adám Jun 20 '18 at 11:08
  • \$\begingroup\$ I posted it here but it was closed due to lack of clarity, and I did not make any further attempts to address the concerns due to lack of spare time at that moment. I would be open to trying again. \$\endgroup\$ – ngm Jun 20 '18 at 15:48
1
\$\begingroup\$

A sort of cyclic program to string together

Write a program that sorts a string.

However, it does some other things too:

  1. When given a non-sorted string (that is not your source code), outputs the string in non-descending ASCII code order, as expected.
  2. When given a sorted string, outputs your program's source code but sorted.
  3. When given your source code but sorted, outputs the original source code.
  4. When given your source code (not sorted), outputs any nonempty string that is none of the above outputs
    • i.e. Your program cannot output a sorted string and therefore must be at least two characters, and it cannot output your original source code

As a result, consider input string -> output string. If you're starting with any non source code unsorted string:

  • The program will start with given unsorted string -> given string sorted. This sorted string can then be input to your program again resulting in given string sorted -> source code sorted
  • If you continue to inputting what the program produced as output, it will then cycle through source code sorted -> source code -> chosen unsorted string -> chosen string sorted -> source code sorted.

Example

Let your program be foobar. Consider the following examples:

-- Case 1 (unsorted string -> sorted string) --

Input:  Programming Puzzles & Code Golf
Output:     &CGPPadeefggillmmnooorrsuzz

Input:  
This is an unsorted string
Hey look a newline
Output: 

       HTaadeeeeghiiiikllnnnnnooorrssssttuwy

-- Case 2 (sorted string -> sorted source code) --

Input:  123ABCDabcd
Output: abfoor

Input:      &CGPPadeefggillmmnooorrsuzz
Output: abfoor

Input:  a
Output: abfoor

-- Case 3 (sorted source code -> unsorted source code) --

Input:  abfoor
Output: foobar

-- Case 4 (unsorted source code -> unsorted string) --

Input:  foobar
Output: a1

Using the last example, if your program outputs a1 as your chosen string, then it will continue to cycle through a1 -> 1a -> abfoor -> foobar -> a1.


Specifications

  • Input and output are both strings
  • Your source code can't already be in sorted order since there are two different actions depending on whether or not it is sorted
  • Standard I/O methods apply and standard loopholes forbidden
  • This is code golf so shortest answer in bytes wins

Sandbox

Usually I have some sort of solution for a challenge but I have absolutely no idea how to go about doing this. I liked the idea though and wanted to know if it's original and if it's clear enough.

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

Reverse Engineering RNG


Intro to both

Pseudorandom number generators are used for simulation and security. While most are appropriate for games and simulations (appropriateness depends on statistical properties), only a select few algorithms are appropriate for security because most of the others are too predictable and can introduce severe vulnerabilities. This challenge should (hopefully) demonstrate how easily some algorithms can be cracked and why the choice of RNG algorithm matters for security.


Cops

Choose/implement/create a pseudorandom number generator, seed it with a constant state, generate the first 10,000 32-bit unsigned integers, and link to it from your post. The robbers will be trying to make a program that generates the same sequence.

Your post should include:

  • The total number of bits of state used by the generator. For example the well-known Mersenne Twister has 19,937 bits of state.
    • Note that if you're using multiple RNG algorithms together, you will have to show the combined count of bits of state.
    • Any randomness used to seed the generator does not count toward this value, though the seed must be constant.
  • A link to the generated sequence of 32-bit unsigned integers

DO NOT post the source code of your generator. That's what the robbers are trying to figure out.

A submission is considered "cracked" if a robber has made a program that generates the exact same sequence. Therefore it is necessary that a robber determine not only the algorithm, but also the initial state of your generator

"Bits of State" Explanation

Every random number generator has a state that is used to determine the next number in the sequence and every number thereafter. Each time a number is used, the state is convoluted in some way and a random number is emitted. The minimum number of binary bits required to store this state will be your "bits of state" count. If you were using a 32-bit linear congruential generator, you would have 32 bits of state. If you were using an LCG with a modulus of 123,456,789, you would have 27 bits of state because 27 bits is the minimum number of bits required to represent every integer between 0 and 123,456,788, inclusive, even if such a state would actually be stored on a 32-bit integer.

Rules and Scoring

  • All state must be self-contained within your generator and your program should generate the exact same sequence every time it is run.
  • You may not use any external sources of entropy, including uninitialized memory, wall time, input, atmospheric noise, network latency, etc...
  • If using an existing algorithm, you will need to make sure to do your research to ensure that the generator meets the above requirements. You may need to seed it manually to ensure that.
  • There are no statistical restrictions on your sequence: it does not have to pass any statistical tests and can fit any distribution you would like, so long as it fits within the range of an unsigned 32-bit integer.
  • The source code to the program used to generate your sequence cannot be larger than 4 KB.
  • A submission that has not been cracked in 168 hours (1 week) will be considered "safe".
  • The "safe" submission with the fewest number of bits of state is the winner.

Robbers

Choose a Cop submission from the other thread (link) and crack its random number generator. It will be considered cracked if you can recreate the sequence exactly.

Rules and Scoring

  • Hard-coding the sequence is not allowed.
  • Your program is limited to 4KB
  • Your generator does not need to have the same state size as long as it generates the same sequence. In practice, this will be necessary unless the RNG used is a really bad algorithm.
  • For each successful crack of a not-yet-safe random number sequence, you will score points according to the number of bits of state used by the generator:
    • 1-32 bits: 1 point
    • 33-128 bits: 2 points
    • 129-1024 bits: 3 points
    • 1025-8192 bits: 5 points
    • 8193-65536 bits: 8 points
    • More than 65536 bits: 13 points
\$\endgroup\$
  • \$\begingroup\$ How would one link a black-box function? \$\endgroup\$ – Jo King Jun 5 '18 at 3:16
  • \$\begingroup\$ @JoKing I'm not quite sure how this is supposed to work. I'm going to have to read up on c&r challenges. \$\endgroup\$ – Beefster Jun 5 '18 at 14:58
  • 3
    \$\begingroup\$ Can you give an objective definition of "non-cryptographically-secure PRNG algorithm"? \$\endgroup\$ – Peter Taylor Jun 6 '18 at 8:53
  • \$\begingroup\$ It seems the algprithm itself can use the seed xor-ed, so giving seed known is useless; but then it's quite bad \$\endgroup\$ – l4m2 Jun 6 '18 at 11:22
  • \$\begingroup\$ @l4m2 That's a good point \$\endgroup\$ – Beefster Jun 6 '18 at 15:53
  • 1
    \$\begingroup\$ How do "bits of state" work? \$\endgroup\$ – l4m2 Jun 6 '18 at 17:51
  • 1
    \$\begingroup\$ "A submission is considered "cracked" if a robber has made a program that generates the exact same sequence. Therefore it is necessary that a robber determine not only the algorithm, but also the initial state of your generator" I don't think so. As I read the question, the robber's generator only has to agree with the cop's for the first 320000 bits output, but unlike the cop the robber has no size limit, so they can hard-code the full 320000 bits. "Hard-coding the sequence is not allowed" is not an objective restriction. \$\endgroup\$ – Peter Taylor Jun 7 '18 at 8:22
  • 1
    \$\begingroup\$ Cop: have an n-bit counter, take the kth byte of sha(MAGIC + counter++). n=12 if you want to bet that the robber can't compress the stream at all; otherwise n=13. The existence of crypto breaks most C&R ideas, but excluding it objectively is tough, and IMO this is a fairly fundamental problem with C&R. \$\endgroup\$ – Peter Taylor Jun 8 '18 at 19:53
  • 1
    \$\begingroup\$ @PeterTaylor That's actually a good point there. I hadn't thought of using a salted hash. That is a trivial "RNG" algorithm that is pretty much unbreakable. I could hard-ban crypto, but there's no way of verifying that and I already have enough on the honor system for cops. sigh \$\endgroup\$ – Beefster Jun 8 '18 at 20:28
  • \$\begingroup\$ There is some sense in which RNG is crypto: a seedable RNG can be used as a stream cipher, although it might not be a good one. \$\endgroup\$ – Peter Taylor Jun 8 '18 at 21:41
  • \$\begingroup\$ So a 1-in-3 and a 1-in-5 is 4 bit or 5 bit? \$\endgroup\$ – l4m2 Jun 13 '18 at 18:28
  • \$\begingroup\$ @l4m2 I'm not sure what you mean \$\endgroup\$ – Beefster Jun 14 '18 at 20:05
1
\$\begingroup\$

Asked

\$\endgroup\$
  • 2
    \$\begingroup\$ Having posted and edited to just contain a link, you can also delete. \$\endgroup\$ – Peter Taylor Jun 13 '18 at 11:09
1
\$\begingroup\$

Add least char to match

Given a string, add at least chars to make the whole string match the given regexp. You can assume it's possible. If there are more than one solution, output a (not necessary uniform) random one.

Here regexp may contain:

|  or
() group
?  possibly not appear
*  may appear for any times. Maybe different in each match
0  
1

Samples

0100      (01)*         010101
0         (0|1)(0|1)    00; 01; 10 (any should possibly appear)
1010      ((0|1)(0|1))* 1010
101       ((0|1)(0|1))* 1010; 1011; 1001; 0101; 1101

\$\endgroup\$
  • \$\begingroup\$ Suggested question text for first para: "Given a string of 0s and 1s, and a regexp: add the minimum number of characters (0s and 1s) that makes the whole string match the given regexp. You can assume that this is possible. If there are multiple solutions of the same length, output any one of them." (This is meant to be a rewording of the same conditions, let me know if I've changed the task in some way with this wording.) \$\endgroup\$ – sundar Jun 16 '18 at 12:10
  • \$\begingroup\$ @sundar Well I did only implied that the string can only contain 0 and 1, 2) I required random, though it may leads to lots of quite strange solutions(generate one that fit, generate another string of same length, if not match return the sure one) \$\endgroup\$ – l4m2 Jun 16 '18 at 12:13
  • \$\begingroup\$ " I did only implied that the string can only contain 0 and 1, 2" <- Are you saying that 2 is also allowed? I don't understand what you're saying here. " I required random, though it may leads to lots of quite strange solutions" <- Can you explain what you mean by random here, exactly? Your sample test case says "any should possibly appear", and that's what my proposed text says at the end ("not necessarily uniform random" seems to be a complicated way of saying the same thing). \$\endgroup\$ – sundar Jun 16 '18 at 12:18
  • \$\begingroup\$ 2) meant it's the second point. "output any of them" seems it can be determistic as the result is valid @sundar \$\endgroup\$ – l4m2 Jun 16 '18 at 12:27
1
\$\begingroup\$

Draw the Recamán's Sequence

Recamán's sequence (A005132) is a mathematical sequence, defined as such:

A(0) = 0
A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else
A(n) = A(n-1) + n

A pretty LaTex version of the above (might be more readable):

pretty latex

The first few terms are 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11

(Description of the sequence borrowed from this older question).

Your task is to animate the drawing this sequence as a series of semi-circles:

Sequence construction

Where each entry above is a keyframe in the animation. Tween frames should draw the circle segment, and if necessary, scale the image down when the new locus would be out of frame.

After 600 terms of the sequence you should have something like this: Pattern (Image from this Numberphile video)

Your choice whether to draw horizontally, vertically, or diagonally, provided that the entire image fits within the image boundary. Line color can be any value, background can be any value (values must be distinct).

Winner

  • The program to generate the most terms of the sequence wins (before the program terminates, crashes, or otherwise corrupts the output--eg by exceeding file size limitations1).
  • Tie will go to the shorter program.

Rules

  • Output image size shall be no smaller than 2048x2048, compiled as a gif, apng, common video format (e.g. mp4), or as an HTML or Javascript canvas (in-place animation).
  • Segments should be drawn over 0.5 second intervals
  • Frame Rate should be no slower than 24 frames/second
  • (That is, each term of the sequence will take at least 12 frames to draw)
  • You need not embed the entire output in your answer, although some means of showing off the results of your work is expected (sped up version, choice stills, etc).

1 If your program will happily produce files in excess of 128 MB (the 64 bit NTFS file system will allow up to 16 TB files), post an altered version of your program that terminates after approximately 128 MB to avoid trashing people's hard drives. You may score based on the unaltered bytecount. Do please post a still image of the final frame your program could otherwise produce (within reason: you not required to generate the entire animation in order to determine true termination). You may use a modified / separate program to produce this still, as it is purely for aesthetic and curiosity purposes.

\$\endgroup\$
  • 2
    \$\begingroup\$ before the program terminates, crashes, or otherwise corrupts the output--eg by exceeding file size limitations ... Segments should be drawn over 0.5 second intervals. Frame Rate should be no slower than 24 frames/second These requirements are heavily dependent on the machine that one uses and therefore are difficult to measure objectively without a person testing every solution; i.e. you, the challenge poster, will have to run all submissions. \$\endgroup\$ – JungHwan Min Jun 19 '18 at 15:09
  • \$\begingroup\$ That's a fair point. \$\endgroup\$ – Draco18s Jun 19 '18 at 15:21
  • \$\begingroup\$ too many rules about time limits, output format, etc, imho \$\endgroup\$ – don bright Jul 7 '18 at 20:11
1
\$\begingroup\$

American Checkers AKA English Draughts

This is a king of the hill challenge for checkers/draughts enthusiasts.

Note: All code below is written in F#

Rules

For this game, I am using the rules from The American Checker Federation (Note: it tries to download a .doc file). The relevant rules are listed below.

Moving

Checkers move forward diagonally one square.
Kings move diagonally one square in any direction.

Capturing

Capturing is required in this variant.
Checkers jump forward diagonally two squares; they may only jump over an opponent's piece onto a blank square and continue jumping until there are no more pieces to jump, or until they reach the king row.

King jumps follow the same pattern as checkers jumps, but do not have the restriction on moving forward.

Winning

The game is won when one player has no more pieces or cannot make any more moves.

Draws

A draw is declared when the same position is reached three times or when neither player moves an unkinged checker for 40 moves and there are no captures in those forty moves.

Play

Each program will take a list of the game history in the form of a PdnTurn list (Read about PDN notation here):

type PieceType = Checker | King
type PdnMove = { Move :int list; ResultingFen :string; DisplayString :string; PieceTypeMoved :PieceType Option }
type PdnTurn = { MoveNumber :int; BlackMove :PdnMove; WhiteMove :PdnMove Option }

It will return the data in the form of a list of ints, where each int represents a square on the board. That is, if you have a piece on square 1 and intend to jump to square 10 over a piece on square 6, your program will return [1; 10] (notation as an F# list). If any player returns an invalid move, they forfeit the game.

Scoring

Each player will play three games against each opponent; each win will be scored as 1, each loss as 0, and each draw as 1/2. The loser of the match will be disqualified. At the end of the tournament, the player(s) with the highest score win.

The Tournament (incomplete):

I set up a website at checkerstreasury.azurewebsites.net. Communication from the server to the player is done with SignalR preferring websockets (you can probably just use websockets without SignalR, but I don't know how). Communication from the player to the server is done with POST requests. I am at work now, but I will post the API and finalize this later.

This challenge feels incomplete; am I missing something?

Question: I have my own AI implemented alongside my controller. I intend on submitting this as a base submission, but will not award it the win even if it is the king of the hill. Should I include it in the question, or as an answer? If an answer, should I post it with the question, or wait a while?

\$\endgroup\$
  • 1
    \$\begingroup\$ In the interests of the challenge being self-contained I'd suggest providing a summary of the rules that would be sufficient for people to complete it without relying on external resources. \$\endgroup\$ – Shaggy Feb 24 '18 at 21:22
  • \$\begingroup\$ @Shaggy Relevant rules added. \$\endgroup\$ – Hosch250 Feb 24 '18 at 23:04
  • \$\begingroup\$ I think Mego has an identical koth? Let me check... \$\endgroup\$ – user202729 Feb 25 '18 at 3:42
  • \$\begingroup\$ Here. \$\endgroup\$ – user202729 Feb 25 '18 at 3:43
  • \$\begingroup\$ Thanks, @user202729. \$\endgroup\$ – Hosch250 Feb 25 '18 at 4:17
  • \$\begingroup\$ Do you intend to post this at some point? I might be interested to write a challenge and a language-agnostic controller (using STDIO and/or argv for I/O), but apparently you and Mego have both created a sandbox post on the same topic. \$\endgroup\$ – PurkkaKoodari May 25 '18 at 23:53
  • \$\begingroup\$ I actually wrote a website for my checkers game over the last few weeks. I'm just working out a few more bugs before it is ready. It has an API for bots to tap in to, and all. Check it out at checkerstreasury.azurewebsites.net (note that steady activity playing the computer by a few users gets it rate-limited as I'm using the free option). \$\endgroup\$ – Hosch250 May 26 '18 at 1:53
  • \$\begingroup\$ Website "done". I'll finalize this soon! \$\endgroup\$ – Hosch250 Aug 4 '18 at 22:36
1
\$\begingroup\$

Execute a Subpar Shuffle™

Inspired by the Execute a Superb Shuffle™ challenge, and a shuffling method I used as a young child before I realised how bad (and time consuming) it is.

In a Subpar Shuffle, you take the deck of cards, and perform the following actions:

  1. Take the top card of the deck and deal it out into a pile.
  2. Take the next card of the deck and place it underneath the deck.
  3. Repeat steps 1 & 2 until you've dealt out the whole deck.

If your deck is represented as a list, then it looks something like this:

  1. Set up an empty list to hold the shuffled list.
  2. Put the first item of the old list at the start of the new list.
  3. Put the first item of the old list at the end of the old list.
  4. Repeat 2 & 3 until the old list is empty, then return the new list.

So, for example, the input list [1, 2, 3, 4] would result in the following:

Old list     | New list
[1, 2, 3, 4] | []
[2, 3, 4]    | [1]          Put the 1 at the start of the new list
[3, 4, 2]    | [1]          Put the 2 at the end of the old list
[4, 2]       | [3, 1]       Put the 3 at the start of the new list
[2, 4]       | [3, 1]       Put the 4 at the end of the old list
[4]          | [2, 3, 1]    Put the 2 at the start of the new list
[4]          | [2, 3, 1]    Put the 4 at the end of the old list
[]           | [4, 2, 3, 1] Put the 4 at the start of the new list

So the final Subpar Shuffled list is [4, 2, 3, 1].

Here are a few more test results for Subpar Shuffling of various lists:

Input                     | Output
[]                        | []
["Ace of Spades"]         | ["Ace of Spades"]
["A","c","e","o","f","S"] | ["o","S","c","f","e","A"]
[1,2,3,4,5,6,7,8,9,0]     | [4,8,0,6,2,9,7,5,3,1]
\$\endgroup\$
  • \$\begingroup\$ Will we be guaranteed that each element in the input list is unique? \$\endgroup\$ – Shaggy Jun 19 '18 at 21:24
  • \$\begingroup\$ That's a fair question. I think that for the purpose of this challenge, I would say yes (although I don't see that it makes much difference). \$\endgroup\$ – ConMan Jun 19 '18 at 23:21
1
\$\begingroup\$

Binary Positional Average

Introduction

(This challenge is from work today) This challenge seems relevant for actual use in the real world, it's a (as far as i know) not yet dealt with kind of integer sequences.

Challenge

  • Inputs: A Integer between 1 and 64 representing the amount of bits to iterate through
  • Output: An Array or a delimiter separated sequence of arrays or sequences of 0s and 1s

The algorithm has to take the input and generate all binary sequences up to the given number ordered by the position of the average 1 bit in the binary representation of the current number. The direction of the sorting is irrelevant. 0 can be ignored.

The solution must terminate, otherwise this is code golf, tiebreaker is performance in program steps.

Example Input and Output

Input:

4

Has (among others) the following possible outputs:

0001,0011,0101,0010,0111,1011,0110,1111,0000,1001,1101,1110,1010,0100,1100,1000

Or:

0001,0011,0111,0010,0101,1011,0110,1111,1001,1101,1010,1110,0100,1100,1000

Example Implementation

(Javascript - modified sketch from work)

function binaryPositionalAverage(size) {

    let srMap = [];

    for (let i = 2**size -1; i > 0; i--) {

        let inp = (i).toString(2);
        let out = "";
        // pad with 0s
        for (let i = 0; i < (size - inp.length); i++) {
            out += "0";
        }
        out += inp;
        out = out.split("").map(s => parseInt(s));
        // out format: [1,1,1,1];

        let rating = 0;
        let divisor = 0; // we ignore 0 by loop condition
        for (let k = 0; k < out.length; k++) {
            if (out[k]) {
                rating += k+1;
                divisor++;
            }
        }
        rating /= divisor;

        srMap.push({
            rating: rating,
            binary: out,
        });
    }
    return srMap.sort((a, b) => a.rating - b.rating).map(e => e.binary);
}
\$\endgroup\$
  • \$\begingroup\$ I find the description rather confusing because of the way it switches between talking about numbers and binary sequences without warning, but I'm pretty sure that the second example output is wrong. Ordering from 0001 to 1000 the order must begin 0001,0011. Then 0010,0101,0111 in any order; then 1011; then 0110,1001,1111 in any order, then 1101; then 0100,1010,1110 in any order; and finally 1100,1000. Plus 0000 somewhere if desired. \$\endgroup\$ – Peter Taylor Jun 19 '18 at 8:46
  • \$\begingroup\$ @PeterTaylor you are right sir, the second output is wrong I'll go ahead and rewrite the challenge later this afternoon to talk about binary representation of numbers, and provide a reference implementation \$\endgroup\$ – S. Janssen Jun 19 '18 at 10:42
  • \$\begingroup\$ Pretty sure this is a dupe but can't quite come up with the right search terms to find it. \$\endgroup\$ – Shaggy Jun 19 '18 at 21:18
  • \$\begingroup\$ @Shaggy I'm not sure, weather i should react to this comment. If the challenge is a dupe, please provide some kind of proof, and I'll delete it; On another note: How would you improve it? \$\endgroup\$ – S. Janssen Jun 19 '18 at 22:35
  • \$\begingroup\$ Does 0 can be ignored mean that 0 can be sorted anywhere in the sequence? Or does it mean that it can be omitted, but if it is included it should be sorted as in the example? \$\endgroup\$ – Emigna Jun 21 '18 at 8:54
  • \$\begingroup\$ What do you mean by The solution must terminate. Only that it can't get stuck in an infinite loop, or do it need to finish for n = 64 within a specific amount of time on a specific set of hardware? I presume it is the former as generating and sorting 18446744073709551616 strings will take a while. \$\endgroup\$ – Emigna Jun 21 '18 at 9:04
1
\$\begingroup\$

A fast-growing evaluator

Introduction

The fast-growing hierarchy is a hierarchy of, well, fast-growing functions, with a one-to-one correspondence to ordinals. If you did some challenges, you may have worked with them, since it's a systematic means of defining functions with extremely fast growth rates.

Here, you are defining as many of them as you can. Of course, because of obvious problems with enumerating them sequentially, the challenge is to yield any particular one given the ordinal, up to as far an upper limit as possible.

The fast-growing hierarchy

If you are lost on some of the jargon here, I recommend a read about ordinals: https://en.wikipedia.org/wiki/Ordinal_number

The fast growing hierarchy is defined for each ordinal in a recursive manner as follows:

  • The lowest and slowest function, corresponding to 0, is f0(n) = n+1.

    • f0(3) = 3+1 = 4
  • For succeeding ordinals and functions in the hierarchy, fa+1(n) = fan(n).

    • f1(2) = f02(2) = f0(f0(2)) = f0(3) = 4
  • For functions in the hierarchy corresponding to limit ordinals, first determine a fundamental sequence that approaches the ordinal in question. Then, fa(n) = fa[n](n), where a[n] is the nth ordinal in the fundamental sequence.

    • The fundamental sequence of ω is {0, 1, 2, 3...}, indexing from zero. So fω(2) = f2(2) = f1(f1(2)) = f1(4) = 8

As can be seen, for infinite-ordinal entries of the fast-growing hierarchy, the value of the function is dependent on the choice of fundamental sequences. Most ordinal notations specify fundamental sequences with the ordinals that they define notations for.

Here are some typical choices of ordinal notations and fundamental sequences, arranged in increasing ordinal-notating capability:

The challenge

Within 1024 bytes, write a program that takes the string representation of an ordinal A in some ordinal interval starting at 0, and a number B of arbitrary size, and prints the fast-growing function corresponding to A, applied to B.

  • Choices of domain of representation, ordinal domain, ordinal notation, and ordinal fundamental sequences must be specified. The choice of fundamental sequences must actually approach the ordinals they define fundamental sequences to, such that logically, the ωth ordinal of that sequence would be the ordinal of that fundamental sequence.
  • The program must provably halt for any input, given sufficient resources, even for invalid inputs or inputs corresponding to ordinals beyond the program's capability. In particular, raw eval() of the input is forbidden, and entries are disqualified if they permit arbitrary code execution.
  • For all given ordinals with the program's capability, the program must print the value as described above for all numbers, deterministically, given enough resources.
  • Standard restrictions on running time and resource usage of programs are relaxed.
  • Competing entries must be able to handle at least A=0.

Scoring

Take C to be the first ordinal for which the program fails to satisfy the requirements above, and D to be the difference between your program byte length and 1024, the maximum byte length of submissions. Then your score is C+D.

Sample scores:

  • Alice, in 200 bytes, writes a program for which A can be any natural number. Her score is ω+824.
  • Bob, in 220 bytes, writes a program for which A can be ω or any natural number. His score is (ω+1)+804 = ω+805.
  • Carol, in 400 bytes, writes a program for which A can be any ordinal purely in Cantor normal form. Her score is ε0+624.
  • Dave, in 700 bytes, writes a program for which A can be a natural number or any epsilon number. His score is ω+324.
  • Eve, in 300 bytes, writes a program which segfaults if A is represented by a decimal string longer than 65536 bytes. Her score is 1065536+724.
\$\endgroup\$
  • \$\begingroup\$ We already have mathjax... \$\endgroup\$ – user202729 Jun 23 '18 at 14:28
  • \$\begingroup\$ @user202729 The challenge is around making a program that can do as asked, to as far a scale as its resources can handle. Of course no computer can have truly infinite resources, but it's the effort to get there that I'm aiming for. The allowance for people to specify their own input, up to reasonable bounds, is to let people specify the infinite ordinals in finite space, say by using the greek letter omega to represent its corresponding ordinal. \$\endgroup\$ – eaglgenes101 Jun 23 '18 at 15:24
  • \$\begingroup\$ However...... you can make your program work for all computable ordinal by make (the notation of an ordinal) = (the function which when given \$n\$ returns the \$n^{th}\$ element in one of its fundamental sequence if it's a limit ordinal, else something contains its pred). \$\endgroup\$ – user202729 Jun 23 '18 at 15:36
  • \$\begingroup\$ The key words are "given enough resources". A program that uses large arrays may choke on a microcontroller but function just fine on a desktop and a supercomputer, and can be designed so it functions essentially the same in the latter two cases, and naturally scales for bigger requirements given more resources. No one will have enough resources to create a computer that can work with some of the hugest defineable numbers, but that doesn't stop people from creating challenges where outputting such huge numbers is the goal of the challenge. \$\endgroup\$ – eaglgenes101 Jun 23 '18 at 15:38
1
\$\begingroup\$

Assign tasks to processors anything better to put here?

Given a list of processor speeds \$S\$, where each element denotes how many ticks the processor at its index takes to complete a task, and a number of tasks \$N\$, replace every element in \$S\$ with the number of tasks the processor at its index should perform. The order of completion doesn't matter, and the tasks aren't enumerated anyway. The processors you pick don't matter either. The only thing that matters is that the ticks needed to complete all the tasks are the least possible. If there are multiple solutions, choose one with the lowest sum of the ticks each processor spends working (less man-hours means happier workers). This is a simple version of such a challenge, so you can assume that every task takes the same amount of time to be completed. You can assume that \$S\$ only consists of positive integers and that its length is at least \$1\$, and \$N\$ is a non-negative integer. What a blob of text...

Examples (test cases)

\$S=[4,1,3,1,2,2,1,1]\\N=13\\\text{Example output: }[0,3,0,3,1,0,3,3]\$

\$S=[8]\\N=28\\\text{Example output: }[28]\$

\$S=[1,1,1,1,1,1,1,1,2]\\N=5\\\text{Example output: }[1,1,1,1,1,0,0,0,0]\$

\$S=[1,28]\\N=28\\\text{Example output: }[28,0]\$
Note that \$[27,1]\$ is an invalid output, since \$1\times27+28\times1>1\times28\$.

\$\endgroup\$
  • \$\begingroup\$ Can I output work time of each processor? (speed × number of work) \$\endgroup\$ – user202729 Jul 6 '18 at 10:18
  • \$\begingroup\$ @Emigna [0, 2, 0, 3, 0] is also invalid. There's [0, 2, 0, 2, 1] which completes all the tasks in 2 ticks, while yours does so only after 3 ticks. The lowest sum is only a tiebreaker, and, if there are still ties, you can choose any possible output. I guess that's not clear enough. \$\endgroup\$ – Erik the Outgolfer Jul 6 '18 at 10:58
  • \$\begingroup\$ @user202729 Sorry, no. It does make some sense, but I don't want a multiple-output challenge. \$\endgroup\$ – Erik the Outgolfer Jul 6 '18 at 11:01
  • \$\begingroup\$ @EriktheOutgolfer: Ah, right. \$\endgroup\$ – Emigna Jul 6 '18 at 11:12
1
\$\begingroup\$

Integers in increasing order of width when printed in Helvetica

XKCD 2016

According to Explain XKCD, Helvetica kerns adjacent 1s together slightly. This means that the sequence of integers in increasing order of width is (0, ) 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10, 12 ... 99, 111, 110, 112 ... 119, 211, 311, 411, 511, 611, 711, 811, 911, 100 ... 109, 120 ... 210, etc.

For the purposes of this question you can assume that repunits will always print wider than numbers with fewer digits. Note that the adjacent pairs may overlap e.g. 11011 has the same width as 11100.

Given an integer n, either return the nth integer in the sequence (you may but do not need to support the 0th integer as 0) or the first n integers (starting at either 0 or 1). Alternatively, print the sequence indefinitely or return a generator or equivalent lazy list.

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

(Should I include negative integers? They could be assumed to be longer than all positive integers with the same number of digits, but shorted than those with more digits.)

\$\endgroup\$
  • 2
    \$\begingroup\$ From explain xkcd: "This sequence is not uniquely defined" ...? Also which is longer, 30 1's or 29 2's? \$\endgroup\$ – user202729 Jul 8 '18 at 3:15
  • \$\begingroup\$ @user202729 "For the purposes of this question you can assume that repunits will always print wider than numbers with fewer digits." \$\endgroup\$ – Neil Jul 8 '18 at 8:45
  • \$\begingroup\$ Still, what about 1111110 and 222220? Both are not repdigits. \$\endgroup\$ – user202729 Jul 8 '18 at 10:59
  • \$\begingroup\$ @user202729 Well, you already know you can assume 111111 is wider than 22222... \$\endgroup\$ – Neil Jul 8 '18 at 16:43
  • \$\begingroup\$ So what? 1 is not shorter than 2, but 11 is shorter than 22. Exactly what are we supposed to do? \$\endgroup\$ – user202729 Jul 8 '18 at 16:44
  • \$\begingroup\$ @user202729 Sort by length and by number of pairs of adjacent 1s. \$\endgroup\$ – Neil Jul 8 '18 at 16:51
  • \$\begingroup\$ I think you should state explicitly that numbers should be first sorted by number of digits then by number of consecutive 1s (if I understood correctly and that is true). \$\endgroup\$ – dylnan Jul 8 '18 at 19:05
  • 1
    \$\begingroup\$ my suggestions. 1. explain what a 'repunit' is. 2. explain what 'kerning' is, actually 3. give a basic explanation of how typesetting works in a computer and how something like this can be measured. 3. specify non-negative integers. 4. is it true that all numbers in helvetica have same width except 1? \$\endgroup\$ – don bright Jul 11 '18 at 1:10
1
\$\begingroup\$

Play a Game of Balls Bounce

The game Balls Bounce consists of the following:

  • a number of blocks, each containing a \$durability\$ number \$\geq 1\$
  • a field of dimension \$h \times w\$, partially filled with blocks (field is \$9\times 7\$ in the example)
  • a number of \$balls\$, positioned in one location at the bottom of the field

Rules of the game:

  • The player chooses a direction in which all the balls will be shot sequentially.
  • Each time a ball hits a block, that block's \$durability\$ decreases by \$1\$.
  • A block that has its \$durability\$ decreased below \$1\$ is removed from the field.
  • Balls that hit a block are deflected and continue to fly. Note that one ball may be deflected multiple times and hit the same block more than once.
  • Balls do not interact with each other directly. They may be in the same place at the same time.
  • If a ball touches the top, left, or right side of the field, it gets deflected in a similar manner.
  • If a ball touches the bottom of the field, it gets stuck there and won't continue to fly this round.
  • A round ends once there are no more balls flying around.
  • After a round ends, all blocks on the field move one row downwards, and new blocks spawn in the top row.
  • The player loses if any block goes past the bottom line.

Note that \$balls\$ might be higher than \$durability\$ of the first block that is hit. In that case, the player now has to keep to paths in mind: the first, a \$durability\$ amount of balls, is deflected by the block, while the second, a \$durability - balls\$ amount passes through the position where the now destroyed block once was.

In the mobile game, the player can choose some angle for the shot. Because I want to make this challenge not bigger than it already is, there is only three possible angles to choose from: 45° to the left, denoted by \$L\$, straight upwards, denoted by \$U\$, and 45° to the right, denoted by \$R\$. Also, the first ball to touch the bottom line marks the position from which the nex round's shot will be taken. For simplicity's sake, all shots will be taken from the middle of the baseline. If a grid has even \$w\$, left of the middle is chosen. If an ambiguity would be created by two balls interacting with the same block at once, the ball that was shot first interacts first.

Input

  • The Field with Blocks

    You may take this as a \$h \times w\$ 2D array of integers or strings. Each value represents the \$durability\$ of the block at that position. You may choose something other than \$0\$ to represent an empty space.
  • The Amount of Balls

    Quite self-explanatory. Integer (or any convenient format).
  • The Direction

    One of \$\{L, U, R\}\$. You may choose the three strings "L", "U" ,"R" to represent this, but any three distinct and consistent values will suffice.

Output

  • Is the game over?

    Output a truthy value if the game is lost after this round, and a falsy one if the game can go on. Any two distinct and consitent values will suffice.

This is , so shortest code in bytes for each language wins.


Example:

Input:

Field

[0][0][0][0][0]
[0][9][0][0][0]
[0][0][1][0][1]
[0][0][0][2][0]

Balls 3

Direction "R"

Output:

False

Step-by-step:

-----------------------
          (1)
-----------------------
#######################   #  border of field
#+---+---+---+---+---+#   
#|   |   |   |   |   |#   +  corner of block/empty cell
#+---+---+---+---+---+#   -  horizontal border of block/empty cell
#|   | 9 |   |   |   |#   |  vertical border of block/empty cell
#+---+---+---+---+---+#   
#|   |   | 1 |   | 1 |#
#+---+---+---+---+---+#
#|   |   |   | 2 |   |#   2  durability
#+---+---+---+---+---+#
###########o###########   o  ball
           3              3  number of balls remaining to be shot

-----------------------
          (2)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   | 1 |   | 1 |#
#+---+---+---+---+---+#
#|   |   |   o 1 |   |#      the first block is hit, durability decreased to 1
#+---+---+--/+---+---+#   /  "tail" to show the direction of the ball
###########o###########
           2

-----------------------
          (3)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   | 0 |   | 1 |#      second block decreased to 0, ball that hit it is deflected
#+---+---+-o-+---+---+#
#|   |   |   o 0 |   |#      same for the first block
#+---+---+--/+---+---+#
###########o###########
           1

-----------------------
          (3)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   |   |   | 1 |#       
#+---+---+-o-+---+---+#
#|   |   o   o   |   |# 
#+---+---+---+---+---+#
###########-###########
           0

-----------------------
          (4)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   o   |   | 1 |#       
#+---+---+---+-o-+---+#
#|   |   |   |   |   |# 
#+---+-o-+---+---+---+#      first ball hit the bottom line...
###########-###########
           0

-----------------------
          (5)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 8 |   |   |   |#
#+---+-o-+---+---+---+#
#|   |   |   |   o 0 |#       
#+---+---+---+---+---+#
#|   |   |   |   |   |# 
#+---+---+---+---+---+#      ... and is removed subsequently
###########-###########
           0

-----------------------
       (6 to 19)
-----------------------
#######################
#+---+-*-+---+---+---+#      *  path of the right ball
#|   *   *   |   |   |#
#+-*-+---+-*-+---+---+#
#*   | 8 |   *   |   |#
#+-*-+---+---+-o-+---+#
#|   o   |   |   |   |#      °  path of the left ball
#+-°-+-*-+---+---+---+#
#°   |   *   |   |   |# 
#+-°-+---+-*-+---+---+#
###########-###########
           0

-----------------------
          (20)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   |   |   |   |   |#      all balls are gone, blocks are shifted down
#+---+-V-+---+---+---+#      no block reaches the bottom line, so no game over
#|   | 8 |   |   |   |#       
#+---+---+---+---+---+#      Return false
#|   |   |   |   |   |# 
#+---+---+---+---+---+#      
###########-###########
           0

The step-by-step diagram is just for illustrative purposes. You are not required to print any of the above.


Sandbox Questions

As this is my first challenge on here, I need some guidance. What examples should be added to clarify the task? What corner cases hould I take into consideration? And most importantly, is it clear what my challenge will be?

\$\endgroup\$
  • \$\begingroup\$ What happens if a ball hits a corner of a block rather than a side? \$\endgroup\$ – AdmBorkBork Jul 11 '18 at 13:16
  • \$\begingroup\$ @AdmBorkBork This is not possible, since the ball always starts in the middle of the bottom of the bottom line's center cell, and move diagonally or vertically. Only the middles of a cell's sides can be hit this way. Should I add an illustration to clarify this? In the original game, if a ball hit a block exactly on the corner, it would be reflected in the opposite direction it came from, taking its path back. I can add this rule, but it should never occur with angles constrained to {45, 90, 135} degrees. \$\endgroup\$ – Orphevs Jul 11 '18 at 14:00
  • \$\begingroup\$ Then maybe just a sentence saying "The ball is guaranteed to never hit a block on the corner." or something, just to completely rule it out. I get what you're saying with the angles, and that makes sense now that I read it again, but it'd be good to have definitive clarification. Nice challenge, otherwise! \$\endgroup\$ – AdmBorkBork Jul 11 '18 at 16:11
  • \$\begingroup\$ @AdmBorkBork Ill think about a way to rephrase my rules so this becomes more clear. Will add your suggestion later when I'm home :) Thank you. \$\endgroup\$ – Orphevs Jul 12 '18 at 1:01
  • \$\begingroup\$ @AdmBorkBork I couldn't think of any corner cases that might come up. Do you have ideas for that? \$\endgroup\$ – Orphevs Jul 12 '18 at 1:05
  • \$\begingroup\$ Corner cases would be things like: A block that can't be reached directly but requires a ricochet to hit, a block by itself on the field, a block that if not hit will result in a game over (that's covered in your example), a field with two blocks that will cause a game over and the balls can only hit one, etc. I would recommend guaranteeing that an empty field will not exist. \$\endgroup\$ – AdmBorkBork Jul 12 '18 at 14:45
1
\$\begingroup\$

Drawing a convex polyiamond

A subtask of Drawing convex polyiamonds. I consider the drawing part hard enough on itself.

A polyiamond is a polygon made from equilateral triangles. For example: (example in ASCII art)

  *
 / \
*---*

Or:

  *---*
 / \ / \
*---*---*
 \ /
  *

(with lines drawn between the triangles for clarity)

While the first polyiamond is convex, the second one is not.


Consider a convex polyiamond. All of its internal angles must be less than 180°. Also, the internal angle of a triangle is 60°, so each vertex must be 60° or 120°.

Assume a polyiamond has all 120° angles. It must have 6 edges.

Given the length of those 6 edges, it's either possible to reconstruct the polyiamond uniquely, or there are no such polyiamond. For example:

(1,1,1,1,1,1) ->

  *---*
 / \ / \
*---*---*
 \ / \ /
  *---*

(1,2,1,2,1,2) ->

  *---*---*
 / \ / \ / \
*---*---*---*
 \ / \ / \ /
  *---*---*
   \ / \ /
    *---*

Now consider a 60° internal angle. It can be assumed to be two consecutive 120° angle with the intermediate edge have length 0. For example:

(0,1,0,1,0,1) ->

  *
 / \
*---*

Your program should take a list of 6 non-negative integers (in any convenient format such as: tuples, string of comma-separated integers, \$2^a 3^b 5^c 7^d 11^e 13^f\$ (for Fractran?)) which represents a valid convex polyiamond, and output the polyiamond as ASCII art.

It's guaranteed that:

  • No numbers in the list will exceed 12.
  • It's guaranteed that there is at least 1 cell in the output. (so (0,0,1,0,0,1) is not a valid input) Equivalently, no two consecutive 0's can appear in the input list.
\$\endgroup\$
  • 1
    \$\begingroup\$ Please upvote this comment if you think the challenge is ready to be posted on main. \$\endgroup\$ – user202729 Jul 17 '18 at 9:07
  • 1
    \$\begingroup\$ Please upvote the post if you think the challenge is interesting, and downvote the post if you think the challenge is not interesting. If the post has enough downvotes I will not post it. \$\endgroup\$ – user202729 Jul 17 '18 at 9:07
  • \$\begingroup\$ Please upvote this comment (or just leave a comment) if you think the challenge has something that needs to be fixed. \$\endgroup\$ – user202729 Jul 17 '18 at 9:07
  • \$\begingroup\$ I have to leave the comments above because it may be unclear how voting in the sandbox works. \$\endgroup\$ – user202729 Jul 17 '18 at 9:09
1
\$\begingroup\$

Given a list of variable names and a list of monomials, output a string representation of the name of the polynomial. The monomials should be represented as pairs [coefficient, vector of exponents] where the vector of exponents has the same length as the list of variable names.

Combine like terms, omit terms that have coefficient zero, and output the resulting polynomial.

If the list of variables is ["x", "y", "z"] then [c, [i,j,k]] represents the monomial c*x^iy^jz^k, so for example [2, [1,2,3]] should be printed as 2xy^2z^3 and [-1, [0,1,2]] should be printed as -yz^2.

A worked example:

Input ["x","y"], [[4,[2,1]], [1,[0,0]], [-1,[1,1]],[-2,[2,1]]]: The monomial [2,1] which corresponds to x^2y is repeated twice, [4,[2,1]] with coefficient 4 and [-2,[2,1]] with coefficient -2 so we add those two coefficients together to get 2x^2y.

[1,[0,0]] corresponds to 1x^0y^0 which should be displayed as 1 and [-1,[1,1]] corresponds to -1x^1y^1 which should be displayed as -xy. The polynomial is the sum of these three, so all together the output should be 2x^2y - xy + 1 or some reordering of these terms.

Requirements:

  • Operators can be surrounded in spaces
  • Like terms should be combined.
  • If the exponent is 1 it should be omitted: x, not x^1. If the exponent is zero, the variable should be omitted entirely: y not x^0y and 1 not x^0y^0.
  • Empty polynomials should be represented as 0.
  • Terms with coefficient zero should be dropped. A coefficient of 1 should be omitted unless all exponents are zero.
  • A negative coefficient should be written with a minus sign. If the first monomial has a positive coefficient, it should not be preceded by a +.
  • Terms can be output in any order

Test Cases

Input: ["x"], [] ==> "0"
Input: [], [[3,[]], [-7,[]]] ==> "- 4"
Input: ["x"], [[0,[5]]] ==> "0"
Input: ["x"], [[1,[5]]] ==> "x^5"
Input: ["x"], [[-1,[5]]] ==> "- x^5"
Input: ["x"], [[1,[5]], [1,[5]]] ==> "2x^5"
Input: ["x"], [[1,[5]], [-1,[5]]] ==> "0"
Input: ["x"], [[1,[2]], [2,[1]], [3,[0]]] ==> "3 + 2x + x^2"
Input: ["x"], [[3,[0]], [2,[1]], [1,[2]]] ==> "3 + 2x + x^2"
Input: ["x", "y", "z"], [[1,[0,0,1]], [1,[1,0,0]], [-1,[0,1,0]]] ==> "x - y + z"
Input: ["x_1", "x_2"], [[1,[1,1]],[1,[2,2]]] ==> "x_1x_2 + x_1^{2}x_2^{2}"
Input: ["x", "y"], [[2,[2,2]], [3,[2,1]], [4,[2,0]], [1,[0,0]], [-1,[1,0]],[-2,[2,0]]] ==> 
        "1 - x + 2x^2 + 3x^2y + 2x^2y^2"
\$\endgroup\$
1
\$\begingroup\$

Syllabification and classification (Venpa)

Introduction

Venpa is a form of classical Tamil poetry, based upon certain rules of metric prosody. The complete rules form a context-free grammar, the task here is to test for a tiny subset of those rules.

Letters

  • Vowels: a, A, i, I, u, U, e, E, y, Y, o, O, W
    • small case represents "short" vowels, CAPS represent "long" vowels
    • y represents the y sound in "my".
    • W represents the "ou" sound in "mouse", and always comes in capital (long) form.
  • Consonant: everything else
    • the consonants can be in small case or capitals, whichever is convenient.

Word Segmenting

Words in the input are seen as composed of segments (which roughly correspond to the usual notion of a syllable). A segment divide occurs where:

  • two or more consonants occur together, tr, rpp, etc.
  • a long (capital) vowel occurs in the word, pO, W, mY etc.
  • two vowels have occurred since the last segment's end (or the word's beginning).

sanjIvi has segments san, jI, vi.
Yvar has Y,var.
vigadakavi has viga,daka,vi.
vAnily has vA,nily.
padAgytAngiha has padA, gytAn, giha
radagajaturagapadAdi has rada, gaja, tura, gapa, dA, di

(Consonants at the end of segments make no difference after segmentation and can be ignored - gytAn=gytA, var=va.)

As you can see, the segments are of two types:

  1. those with a single vowel, san, Y, vA, called a straight (S) segment
  2. those with two vowels, viga, nily, padA called a sequence (Q) segment

So the segment patterns of the above words are:

  sanjIvi              =              san + jI + vi          = SSS
  Yvar                 =                 Y + var             = SS
  vigadakavi           =            viga + daka + vi         = QQS
  vAnily               =                vA + nily            = SQ
  padAgytAngiha        =           padA + gytAn + giha       = QQQ
  radagajaturagapadAdi = rada + gaja + tura + gapa + dA + di = QQQQSS

Permitted patterns

The rules for words allowed in a Venpa are:

  1. a word should have one to three segments
  2. a one or two segment word can have any pattern (S, Q, SQ, SS, QS, QQ)
  3. a three segment word must end in a straight (S) segment

So out of the above, SSS, SS, QQS, and SQ are allowed, QQQ and QQQQSS are not.

Task

Given an input word in the above letters, output its segment pattern if it's an allowed word, or a false-y value if it's not an allowed word.

Input

  • Will be a single word composed of the characters mentioned under the Letters heading above
    • (Small case w will not be present anywhere in the text (neither as a vowel nor as a consonant))

Output

  • The segment pattern of the input word, if it's an allowed word
    • can use any two distinct unambiguous characters to represent S segments and Q segments
  • A false-y value in your language if it's not an allowed word
  • Output is undefined for invalid input (i.e. has characters other than those specified)

Test cases

vigadakavi 
=> QQS
Yvar 
=> SS
padAgytAngiha
=> falsey (QQQ not allowed)
vAnily
=> SQ
katradanA
=> SQS
radagajaturagapadAdi 
=> falsey (more than 3 segments)
TuppArkkuT
=> SSS
mazai
=> Q
\$\endgroup\$
  • 1
    \$\begingroup\$ fascinating. im probably very unusual, but i would like it even better if it was actual poetry instead of 'p' everywhere, maybe even in tamil script (although that would probably disqualify some languages) \$\endgroup\$ – don bright Jul 7 '18 at 2:37
  • 1
    \$\begingroup\$ Yeah, I intended to just remove some extraneous complexity, but somehow having input in this form makes it slightly less interesting even to me (and I'm not sure it removes a meaningful level of complexity anyway, relative to the rest of the task). I'll change it to use the actual consonants if anyone else here also feels this way. (The last two test case inputs are from actual poetry by the way, just with the consonants replaced.) \$\endgroup\$ – sundar Jul 7 '18 at 18:54
  • 1
    \$\begingroup\$ Using Tamil script would also be great, but my concern with that is mainly that it might make testing and debugging much harder for people who can't read the script. I can mitigate some of that by providing exhaustive test cases, but I'm not sure it's worth it. \$\endgroup\$ – sundar Jul 7 '18 at 18:58
  • \$\begingroup\$ yeah i think i might be a little unusual in my tastes, i still like the puzzle... \$\endgroup\$ – don bright Jul 7 '18 at 20:08
  • 1
    \$\begingroup\$ @donbright I've updated the post to use different consonants (corresponding to actual words). I like this version a lot better, but let's see how it's received. \$\endgroup\$ – sundar Jul 20 '18 at 14:18
  • \$\begingroup\$ I wrote a program that solves the examples you gave. my first pass was 60 lines of Rust code. i think it is a really good puzzle, great balance between an interesting puzzle and many ways to possibly reduce code size. very interesting. \$\endgroup\$ – don bright Dec 29 '18 at 14:10
  • \$\begingroup\$ i would like some more examples though. feel like my program might be wrong on some inputs. \$\endgroup\$ – don bright Dec 29 '18 at 14:11

You must log in to answer this question.

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