571
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

\$\endgroup\$
1
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    May 15 at 14:05

4686 Answers 4686

1
139 140
141
142 143
157
0
\$\begingroup\$

Output a 1-digit integer log table

Log tables were originally used for multiplication, since \$ x \times y = \exp(\log x + \log y) \$, superseding the use of trigonometric functions for this purpose. A log table I used in school back in the day had 900 main entries and then some interpolation entries you could use to give yourself almost an extra digit of accuracy.

However, if you were building a mechanical computer, you wouldn't need to have thousands of entries, as you could just program it to do long multiplication; the stumbling block is actually multiplying two digits together in the first place.

One approach to this is to use something called an Irish logarithm table. This is basically a pair of integer mappings \$ f \$ and \$ g \$ such that \$ g(f(x) + f(y)) = x \times y \$ for all \$ x, y \in \{ 0..9 \} \$.

For this challenge I would like you to output any two integer mappings with that property, in any reasonable format. In particular, since the length of the f mapping is always ten, there is no need to separate the f and g mappings in your output.

Note that while the f mapping maps from 0 to 9, the g mapping will have gaps because some of its indices won't correspond to the sum of two values of f. You can handle this either by outputting the mapping as a dictionary or by padding the output array with a suitable filler value.

Excluding the filler value, the g mapping only needs to output the values 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72, 81.

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

\$\endgroup\$
9
  • \$\begingroup\$ Any potentially shorter way than log(x)*999? \$\endgroup\$
    – l4m2
    Dec 31, 2023 at 0:41
  • \$\begingroup\$ @l4m2 What integer are you using for an input of 0? \$\endgroup\$
    – Neil
    Dec 31, 2023 at 0:59
  • \$\begingroup\$ Also, I can see I should have specified non-negative integers. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 1:03
  • \$\begingroup\$ And I might need to include the highest index of g in the scoring somehow. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 1:04
  • \$\begingroup\$ Is there a reason for outputting mappings and not just implementing the functions? \$\endgroup\$ Dec 31, 2023 at 4:30
  • \$\begingroup\$ @CommandMaster It's to help you construct a mechanical calculator which can do lookup tables but not function calls. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 8:18
  • \$\begingroup\$ I just don't think that requiring answers to do return [f(i) for i in range(10)] is interesting - do you have solutions constructing these mappings in a different way? \$\endgroup\$ Dec 31, 2023 at 9:12
  • \$\begingroup\$ @CommandMaster I wasn't expecting there to be a closed form for f and g; if you have one then this question becomes irrelevant. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 9:41
  • \$\begingroup\$ There is discrete log mod 83, although that isn't really a closed form and you need to do something for 0 \$\endgroup\$ Dec 31, 2023 at 10:11
0
\$\begingroup\$

Golf golfing a range with modulus and subtraction

In this other question I asked you to golf code which finds an equation transforming a list of unique numbers down to a minimal list. For this question, I'm asking you to write code which golfs that equation. In the other question we found that ((l-5)%99-94)%98 is a valid equation that turns l=[2,1,5,3,99,7,6] into [2,1,4,3,0,6,5], but if we do some more thinking, we can see that there are shorter ways to do this: (l%91-5)%8 gives the list [5,4,0,6,3,2,1] and l%95-1 gives the list [1,0,4,2,3,6,5]. Rather than golfing the code used to generate the equation, in this question you are looking for an algorithm that produces the shortest final equation.

To be a valid answer, your code must give an equation that transforms a provided list of unique, non-negative integers into a list of unique, non-negative integers in the range 0 to len(list)-1. You are scored for the length of the equation that you output rather than the length of your code. Each operation is one point, so an output of ((l-5)%99-94)%98 would score 4, (l%91-5)%8 would score 3, and l%95-1 would score 2. In a tie, the score is the character length of the complete equation including parenthesis, so ((l-5)%99-94)%98 would score 16, (l%91-5)%8 would score 10, and l%95-1 would score 6. Lowest score wins, as with normal code golf.

Different lists may give better scores using some algorithms over others, so we need to test your code to be sure that it is the best for many different lists. The score you list on your answer is the average score your code gets on all lists of 1-15 digits with values in the range 0-63 (say the average primary and secondary score in your answer). As this question is about the algorithm rather than the code length, you should explain your method as well. If you can prove that your method will always give the best possible score, I will mark your answer as accepted and (if it's simple enough) use your method as the example explanation in the other question. If this happens, I will also edit this question to include an explanation of your algorithm and this question will become a normal code-golf question where everyone implements that algorithm or an equivalent in as few bytes as possible in each language.

As the lists your code is tested against are finite in length and have a maximum value, you could theoretically brute-force the shortest solution by trying every possible modulus and subtraction value and returning the shortest. To prevent this, your code should run in less than O(r^l) time, where r is the range and l is the length.

@sandbox, What do you think is a good range? Should it be 1-7 digits, 1-31 digits? Values from 0-31, values from 0-127? Or should it be decimal ranges, 1-9 digits ranging from 0-99?

Also, what other tags?

\$\endgroup\$
6
  • \$\begingroup\$ Is there anything preventing solutions from doing a boring, trivially optimal, bruteforce solution? \$\endgroup\$ Dec 23, 2023 at 2:48
  • \$\begingroup\$ @CommandMaster do you think that looks good for preventing bruteforce solutions? \$\endgroup\$
    – guest4308
    Dec 24, 2023 at 4:33
  • 1
    \$\begingroup\$ Requiring to build the equation one operand at a time seems overly restrictive, and it's also not very clearly defined. What kind of calculations can you do on the array, before you actually "build" the solution? \$\endgroup\$ Dec 24, 2023 at 4:56
  • \$\begingroup\$ @CommandMaster yeah, I think that worked better in my head than it would in practice. I can't think of any other way to restrict bruteforce solutions without also restricting algorithmic solutions, do you have any ideas? or if not; is it fine to just have 'the brute force solution does not count' in the question? \$\endgroup\$
    – guest4308
    Dec 24, 2023 at 5:03
  • \$\begingroup\$ I think the best way to prevent brute force would just be to restrict the runtime, and have larger inputs \$\endgroup\$ Dec 24, 2023 at 5:04
  • \$\begingroup\$ @CommandMaster do you think that works to prevent bruteforce? and also for larger inputs what were you thinking would be a good amount? I think rn it's checking around 2e14 lists \$\endgroup\$
    – guest4308
    Dec 26, 2023 at 14:59
0
\$\begingroup\$

Unnecessary fluff

Sandbox note

There is a fairly efficient way to calculate this \$h\$, which might be interesting. Do you think I should require polynomial time, or being able to calculate all the testcases in a minute?

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

Shortest path to open a letter lock

\$\endgroup\$
4
  • \$\begingroup\$ I think this is easier than you intend it to be, but fair enough. Can the input be taken as a list of indices of the alphabet rather than a string / list of codepoints? \$\endgroup\$
    – noodle man
    Jan 6 at 22:45
  • \$\begingroup\$ @noodleman i think that would ruin the theme here, i wasnt even sure if i should include the list of letters instead of the full string \$\endgroup\$
    – pacman256
    Jan 7 at 0:06
  • 1
    \$\begingroup\$ Well, taking a string as a list of characters is an I/O default on this site. I would personally recommend letting letters of the alphabet be taken as indices, as that's just an extra step that most solutions will have to use and could be very long in some languages. Alternatively, a slightly more interesting variant of this challenge would be to take an arrangement of the alphabet as input (like abc...z or azbycx... or ajoifqw...) rather than always using the same alphabet. \$\endgroup\$
    – noodle man
    Jan 7 at 1:34
  • \$\begingroup\$ @noodleman From what I have seen, allowing letters to be replaced with indices is generally not an option for input in challenges like this, especially when the whole point is to have two "words" to switch between \$\endgroup\$
    – pacman256
    Jan 7 at 4:55
0
\$\begingroup\$

Circle to split points

Given two sets of points, decide whether there's a circle that split them.

  • Treating points exactly on circle as inside or outside are allowed as radius +/-eps

  • Maybe one input forced inside and one outside?

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

The Elements Of The Periodic Table!

The challenge is to take input as an integer between 1 and 118 inclusive, then output the name of the chemical element with that atomic number.

Capitalisation as well as trailing and leading whitespace do not matter.

You should call the chemical elements by their 2024 names, for example 113 outputs nihonium and not ununtrium.

For ease of golfing, element 16 can be either sulfur or sulphur.

Test cases:

1 -> hydrogen
2 -> helium
3 -> lithium
4 -> beryllium
5 -> boron
6 -> carbon
117 -> tennessine
118 -> oganesson

Use any language, shortest code in bytes wins.

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

Find the child anagrams of a word

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

Battle Simulator KOTH

Challenge

In this king-of-the-hill challenge, each player/bot is assigned a random character and is then put in a 10x10 grid. Each character has 2 different abilities and 1 ultimate ability. The goal of each player is to be the last man standing.

Rules

At the start of each game, each bot is given 10 health and 10 points to freely distribute through these 3 categories:

Speed (for example if you have three speed you can go up 2 and left 1 in one turn)

Dexterity (the more dexterity you have the less chance you have of getting hit by an attack. For example if you have 3 dexterity and was attacked by an attack that does 4 damage, there is a 3 * 3 = 9% chance you dodge it where the second 3 is a constant.)

Defense (let's say you have 3 defense and was hit by an attack that does 5 damage. Then you will take a random amount of damage from 1 to 1 where the second 1 is attack strength - defense / 2)

Each bot is also randomly assigned one of these two characters:

Swordsman:

  • Normal ability (Stab):
    • 0 (turns of) recharge
    • does 1 damage
    • hits the three tiles in front of him
  • Special ability 1 (Circle Slash):
    • 2 recharge
    • does 2 damage
    • hits the 9 tiles surrounding him
  • Special ability 2 (Multi-Sword):
    • 4 recharge
    • does 2 damage
    • hits the three closest enemies
  • Ultimate Ability (Explosion):
    • 10 recharge (cannot be used at beginning of game)
    • does 6 damage
    • hits the first player in front of him and triggers a 6x6 explosion

Wizard

  • Normal ability (Burn):
    • 0 recharge
    • does 2 damage
    • hits the tile directly in front of him
  • Special ability 1 (Freeze):
    • 3 recharge
    • does 1 damage
    • freezes the first enemy in front of him for 2 turns
  • Special ability 2 (Zap):
    • 5 recharge
    • does 2 damage
    • zaps the five closest enemies, twice
  • Ultimate ability (Weaken):
    • 15 recharge (cannot be used at the beginning of game)
    • 0 damage
    • halves all stats of all other players (can stack)

However, there is a twist. Each bot does NOT know what character type they are.

Turns

Each turn, every player does one of the following:

  • Do nothing (lol)
  • Use an attack that is not on cooldown (attacks can miss)
  • Move

When a player is hit by an attack, their health goes down by how strong the attack is and is also hit by status effects should the attack have them. If a player's health reaches zero, they are defeated (e. g. removed from the game) and are replaced by a rock other players may not pass through. If a player tries to move through a rock or another player, they simply end up in front of it and do not go through.

The game ends in 100 turns or only one player remains, whichever comes first. If the game lasts that long, the winner is the one with most eliminations. If there still is a tie, all tied bots receive a point for that round. Of course, if only one player remains before the 100 turns, that player wins the round and gets a point.

How bots work

Bots should be written in Python, but I will try to support other mainline languages by translating them into Python.

The basic boilerplate code for a bot is this:

class MyBotThatWillHopefullyWin(Bot):
    def __init(self)__:
        super().__init__(self, <speed>, <dexterity>, <defense>)
    
    def turn():
        <insert logic>

The turn function is basically your main function and will be executed for every turn your bot is alive for. It should return one of four values:

  • return "move", <x>, <y> to move (duh.) Or in more specific terms, Tuple[Union[str, Union[int, int]]] where str must be move and abs(x + y) must be <= self.speed (the first value you put in the super definition.) If this condition is not satisfied, nothing happens that turn. Note how you cannot leave the confines of the 10x10 grid or move and attack or vice versa in the same turn.

  • return "basic attack" to do the (randomly predetermined) charector's basic attack.

  • return "ability", <ability number> to do one of the charector's abilities. 1 is the charector's first special ability, 2 is the second, and 3 is the ultimate ability. If the ability numberis not in the range 1-3 or the attack is still on cooldown, nothing happens.

  • return "nothing" to do nothing. But why tho?

Here is the list of methods bots have available to them: (accessed by self.<method name(<parameters, if any>)

\$\endgroup\$
2
  • \$\begingroup\$ What do players know? Only the location of enemies and whether they're dead, and their own health? \$\endgroup\$ Jan 18 at 3:44
  • \$\begingroup\$ @CommandMaster I'll add that in when I have the time. \$\endgroup\$ Jan 18 at 14:56
0
\$\begingroup\$

ahee bee cee dee ehee fee...

Given a string with no whitespace, replace the first letter of the string with every letter in the english lowercase alphabet. However, if the input string starts with a vowel (excluding y), then there should be an extra h after (the prefixes aeiou.)

For example, if the input string is ee, your program should output:

ahe
be
ce
de
ehe
fe
ge
he
ihe
je
ke
le
me
ne
ohe
pe
qe
re
see
te
uhe
ve
we
xe
ye
ze
\$\endgroup\$
2
  • \$\begingroup\$ Where do eht come? \$\endgroup\$
    – l4m2
    Jan 22 at 2:35
  • \$\begingroup\$ @I4m2 Should be fixed now. \$\endgroup\$ Jan 22 at 14:28
0
\$\begingroup\$

What are the current football (soccer) league positions?

English football is structured into leagues with varying numbers of clubs. For example, the EFL Championship has 24 clubs. During each season, each side will play every other side twice (once at home and once away); for a 24-club league, this gives 46 matches for each team in total. Teams score three points for a win, one for a draw and none for a loss. The ranking in the league is determined by:

  1. Points gained
  2. Goal difference
  3. Goals scored
  4. Head-to-head record
  5. Alphabetical order (unless the position is relevant for a promotion, relegation or play-off space, but this has never happened, and will not need to be handled for this challenge)

Challenge

Input

  • A list of games played so far in the league, indicating the home team, away team, score for the home team and score for the away team.

Desired output

  • A list of teams in position order, either highest to lowest or lowest to highest (but must be consistent for all inputs).

Rules and assumptions

  • Teams can be represented in whatever way the answerer prefers. You may take actual team names, integers, or any other standard input provided the team name does not somehow encode its position in the league and none of the default loopholes are violated. Team names in the output should match those in the input.
  • All teams in the league will have played at least once at the time of asking, though they will not necessarily have all played each other by that stage, nor will they have necessarily played the same number of matches. Of note, the interim league tables for English football show the number of matches played, but the relative positioning does not take into account that one team may have matches in hand.
  • You do not need to provide any of the stats typically presented in a football league table, just the ordering of teams.
  • Default loopholes and standard I/O methods apply
  • Although input is flexible, the home/away ordering should be preserved (so it is not valid to require the winning team always be listed first)
  • This is so the shortest code in bytes wins!

Example input

[
[["Leeds United",2],["Preston North End",1]],
[["Plymouth Argyle",3],["Cardiff City",1]],
[["Middlesbrough",1],["Rotherham United",1]],
[["Norwich City",2],["West Bromwich Albion",0]],
[["Stoke City",1],["Birmingham City",2]],
[["Queens Park Rangers",2],["Millwall",0]],
[["Sheffield Wednesday",1],["Coventry City",2]],
[["Blackburn Rovers",1],["Huddersfield Town",1]],
[["Bristol City",1],["Watford",1]],
[["Swansea City",1],["Southampton",3]],
[["Sunderland",0],["Hull City",1]],
[["Queens Park Rangers",1],["Watford",2]],
[["Ipswich Town",2],["Sunderland",1]],
[["Millwall",1],["Middlesbrough",3]],
[["Rotherham United",0],["Stoke City",1]],
[["Southampton",4],["Sheffield Wednesday",0]],
[["West Bromwich Albion",4],["Blackburn Rovers",1]],
[["Huddersfield Town",1],["Plymouth Argyle",1]],
[["Cardiff City",0],["Leeds United",3]],
[["Birmingham City",2],["Swansea City",2]],
[["Preston North End",2],["Bristol City",0]],
[["Coventry City",3],["Leicester City",1]],
[["Hull City",1],["Norwich City",2]],
[["Sheffield Wednesday",3],["Hull City",1]],
[["Norwich City",1],["Southampton",1]],
[["Blackburn Rovers",2],["Rotherham United",2]],
[["Bristol City",0],["Millwall",1]],
[["Leeds United",3],["Birmingham City",0]],
[["Leicester City",4],["Huddersfield Town",1]],
[["Middlesbrough",1],["Coventry City",3]],
[["Plymouth Argyle",3],["Watford",3]],
[["Stoke City",0],["Ipswich Town",0]],
[["Swansea City",1],["West Bromwich Albion",0]],
[["Queens Park Rangers",1],["Cardiff City",2]],
[["Sunderland",2],["Preston North End",0]],
[["West Bromwich Albion",1],["Leeds United",0]],
[["Ipswich Town",0],["Queens Park Rangers",0]],
[["Cardiff City",0],["Leicester City",2]],
[["Coventry City",2],["Swansea City",2]],
[["Huddersfield Town",1],["Middlesbrough",2]],
[["Hull City",3],["Blackburn Rovers",2]],
[["Rotherham United",1],["Sunderland",1]],
[["Millwall",1],["Norwich City",0]],
[["Preston North End",0],["Sheffield Wednesday",1]],
[["Watford",1],["Stoke City",1]],
[["Birmingham City",0],["Bristol City",0]],
[["Southampton",2],["Plymouth Argyle",1]],
[["Ipswich Town",1],["Leicester City",1]],
[["Birmingham City",1],["Stoke City",3]],
[["Rotherham United",1],["Middlesbrough",0]],
[["Southampton",5],["Swansea City",0]],
[["Hull City",0],["Sunderland",1]],
[["Huddersfield Town",3],["Blackburn Rovers",0]],
[["Coventry City",2],["Sheffield Wednesday",0]],
[["Cardiff City",2],["Plymouth Argyle",2]],
[["West Bromwich Albion",1],["Norwich City",0]],
[["Watford",1],["Bristol City",4]],
[["Millwall",2],["Queens Park Rangers",0]],
[["Preston North End",2],["Leeds United",1]],
[["Stoke City",0],["Millwall",0]],
[["Sunderland",0],["Coventry City",3]],
[["Sheffield Wednesday",1],["Cardiff City",2]],
[["Leicester City",3],["Rotherham United",0]],
[["Queens Park Rangers",0],["Southampton",1]],
[["Plymouth Argyle",3],["Birmingham City",3]],
[["Norwich City",2],["Huddersfield Town",0]],
[["Middlesbrough",1],["West Bromwich Albion",0]],
[["Blackburn Rovers",1],["Watford",2]],
[["Leeds United",4],["Ipswich Town",0]],
[["Swansea City",2],["Preston North End",1]],
[["Bristol City",3],["Hull City",2]],
[["Birmingham City",2],["Leicester City",3]],
[["West Bromwich Albion",1],["Stoke City",1]],
[["Plymouth Argyle",3],["Rotherham United",2]],
[["Swansea City",1],["Middlesbrough",2]],
[["Southampton",4],["Blackburn Rovers",0]],
[["Sheffield Wednesday",2],["Queens Park Rangers",1]],
[["Preston North End",1],["Watford",5]],
[["Millwall",1],["Huddersfield Town",1]],
[["Leeds United",1],["Coventry City",1]],
[["Hull City",3],["Cardiff City",0]],
[["Bristol City",1],["Sunderland",0]],
[["Ipswich Town",2],["Norwich City",2]],
[["Middlesbrough",1],["Hull City",2]],
[["Cardiff City",0],["Birmingham City",1]],
[["Coventry City",1],["Southampton",1]],
[["Norwich City",3],["Sheffield Wednesday",1]],
[["Leicester City",3],["Millwall",2]],
[["Queens Park Rangers",0],["Plymouth Argyle",0]],
[["Sunderland",1],["Leeds United",0]],
[["Watford",1],["Ipswich Town",2]],
[["Stoke City",1],["Swansea City",1]],
[["Rotherham United",0],["West Bromwich Albion",2]],
[["Huddersfield Town",1],["Preston North End",3]],
[["Blackburn Rovers",2],["Bristol City",1]],
[["Norwich City",0],["Preston North End",0]],
[["Cardiff City",1],["Millwall",0]],
[["Leicester City",4],["Plymouth Argyle",0]],
[["Middlesbrough",0],["Ipswich Town",2]],
[["Huddersfield Town",1],["Bristol City",1]],
[["Queens Park Rangers",2],["Hull City",0]],
[["Stoke City",0],["Sheffield Wednesday",1]],
[["Watford",1],["Southampton",1]],
[["Rotherham United",1],["Swansea City",2]],
[["Sunderland",2],["West Bromwich Albion",1]],
[["Blackburn Rovers",0],["Leeds United",2]],
[["Coventry City",2],["Birmingham City",0]],
[["Bristol City",1],["Norwich City",2]],
[["Millwall",1],["Sunderland",1]],
[["Birmingham City",0],["Rotherham United",0]],
[["Hull City",1],["Watford",2]],
[["Ipswich Town",2],["Coventry City",1]],
[["Leeds United",3],["Middlesbrough",2]],
[["Swansea City",1],["Huddersfield Town",1]],
[["Plymouth Argyle",2],["Stoke City",1]],
[["Sheffield Wednesday",3],["Blackburn Rovers",1]],
[["Southampton",2],["Cardiff City",0]],
[["West Bromwich Albion",1],["Leicester City",2]],
[["Preston North End",0],["Queens Park Rangers",2]],
[["Ipswich Town",3],["Millwall",1]],
[["Blackburn Rovers",4],["Birmingham City",2]],
[["Leeds United",3],["Swansea City",1]],
[["Sheffield Wednesday",1],["Leicester City",1]],
[["Southampton",1],["Bristol City",0]],
[["Sunderland",1],["Huddersfield Town",2]],
[["Watford",3],["Norwich City",2]],
[["Queens Park Rangers",4],["Stoke City",2]],
[["Middlesbrough",4],["Preston North End",0]],
[["Hull City",4],["Rotherham United",1]],
[["Coventry City",1],["Plymouth Argyle",0]],
[["Cardiff City",0],["West Bromwich Albion",1]],
[["West Bromwich Albion",2],["Ipswich Town",0]],
[["Millwall",0],["Coventry City",3]],
[["Birmingham City",2],["Sheffield Wednesday",1]],
[["Bristol City",3],["Middlesbrough",2]],
[["Huddersfield Town",1],["Southampton",1]],
[["Leicester City",2],["Watford",0]],
[["Norwich City",1],["Queens Park Rangers",0]],
[["Preston North End",1],["Cardiff City",2]],
[["Stoke City",0],["Blackburn Rovers",3]],
[["Swansea City",2],["Hull City",2]],
[["Plymouth Argyle",2],["Sunderland",0]],
[["Rotherham United",1],["Leeds United",1]],
[["Cardiff City",2],["Norwich City",3]],
[["Leeds United",2],["Plymouth Argyle",1]],
[["Coventry City",0],["Stoke City",0]],
[["Hull City",1],["Huddersfield Town",0]],
[["Ipswich Town",3],["Swansea City",2]],
[["Southampton",2],["West Bromwich Albion",1]],
[["Middlesbrough",1],["Leicester City",0]],
[["Queens Park Rangers",0],["Bristol City",0]],
[["Sheffield Wednesday",0],["Millwall",4]],
[["Watford",5],["Rotherham United",0]],
[["Sunderland",3],["Birmingham City",1]],
[["Blackburn Rovers",1],["Preston North End",2]],
[["Rotherham United",2],["Ipswich Town",2]],
[["Norwich City",1],["Blackburn Rovers",3]],
[["West Bromwich Albion",3],["Hull City",1]],
[["Swansea City",0],["Sunderland",0]],
[["Birmingham City",2],["Ipswich Town",2]],
[["Bristol City",1],["Sheffield Wednesday",0]],
[["Huddersfield Town",0],["Watford",0]],
[["Rotherham United",1],["Queens Park Rangers",1]],
[["Millwall",0],["Southampton",1]],
[["Plymouth Argyle",3],["Middlesbrough",3]],
[["Preston North End",3],["Coventry City",2]],
[["Stoke City",0],["Cardiff City",0]],
[["Leicester City",0],["Leeds United",1]],
[["Coventry City",0],["West Bromwich Albion",2]],
[["Sheffield Wednesday",2],["Rotherham United",0]],
[["Ipswich Town",3],["Plymouth Argyle",2]],
[["Blackburn Rovers",0],["Swansea City",1]],
[["Cardiff City",2],["Bristol City",0]],
[["Hull City",1],["Preston North End",0]],
[["Middlesbrough",0],["Stoke City",2]],
[["Queens Park Rangers",1],["Leicester City",2]],
[["Sunderland",3],["Norwich City",1]],
[["Watford",2],["Millwall",2]],
[["Leeds United",4],["Huddersfield Town",1]],
[["Southampton",3],["Birmingham City",1]],
[["Stoke City",1],["Leeds United",0]],
[["Rotherham United",2],["Coventry City",0]],
[["Preston North End",2],["Southampton",2]],
[["Plymouth Argyle",3],["Sheffield Wednesday",0]],
[["Bristol City",0],["Ipswich Town",1]],
[["Birmingham City",0],["Hull City",2]],
[["West Bromwich Albion",2],["Queens Park Rangers",0]],
[["Leicester City",1],["Sunderland",0]],
[["Swansea City",0],["Watford",1]],
[["Norwich City",1],["Middlesbrough",2]],
[["Millwall",1],["Blackburn Rovers",2]],
[["Huddersfield Town",0],["Cardiff City",4]],
[["Middlesbrough",1],["Birmingham City",0]],
[["Blackburn Rovers",1],["Cardiff City",0]],
[["Bristol City",1],["Coventry City",0]],
[["Huddersfield Town",2],["Queens Park Rangers",1]],
[["Hull City",1],["Southampton",2]],
[["West Bromwich Albion",0],["Plymouth Argyle",0]],
[["Norwich City",2],["Leeds United",3]],
[["Stoke City",2],["Sunderland",1]],
[["Swansea City",1],["Leicester City",3]],
[["Watford",1],["Sheffield Wednesday",0]],
[["Preston North End",1],["Millwall",1]],
[["Cardiff City",1],["Watford",1]],
[["Southampton",1],["Rotherham United",1]],
[["Sheffield Wednesday",0],["Huddersfield Town",0]],
[["Queens Park Rangers",0],["Blackburn Rovers",4]],
[["Plymouth Argyle",1],["Swansea City",3]],
[["Millwall",2],["Hull City",2]],
[["Leicester City",2],["Stoke City",0]],
[["Leeds United",2],["Bristol City",1]],
[["Ipswich Town",4],["Preston North End",2]],
[["Coventry City",1],["Norwich City",1]],
[["Sunderland",0],["Middlesbrough",4]],
[["Birmingham City",3],["West Bromwich Albion",1]],
[["Rotherham United",1],["Bristol City",2]],
[["Sunderland",2],["Watford",0]],
[["Leicester City",3],["Preston North End",0]],
[["Leeds United",1],["Queens Park Rangers",0]],
[["Coventry City",1],["Blackburn Rovers",0]],
[["Swansea City",2],["Norwich City",1]],
[["West Bromwich Albion",1],["Sheffield Wednesday",0]],
[["Stoke City",0],["Southampton",1]],
[["Plymouth Argyle",0],["Millwall",2]],
[["Middlesbrough",2],["Cardiff City",0]],
[["Ipswich Town",3],["Hull City",0]],
[["Birmingham City",4],["Huddersfield Town",1]],
[["Blackburn Rovers",1],["Leicester City",4]],
[["Huddersfield Town",1],["Ipswich Town",1]],
[["Millwall",0],["Swansea City",3]],
[["Cardiff City",2],["Rotherham United",0]],
[["Bristol City",2],["Stoke City",3]],
[["Hull City",1],["Plymouth Argyle",1]],
[["Norwich City",2],["Birmingham City",0]],
[["Queens Park Rangers",1],["Coventry City",3]],
[["Watford",2],["Middlesbrough",3]],
[["Preston North End",0],["West Bromwich Albion",4]],
[["Southampton",3],["Leeds United",1]],
[["Sheffield Wednesday",0],["Sunderland",3]],
[["Coventry City",1],["Huddersfield Town",1]],
[["Sunderland",0],["Cardiff City",1]],
[["Stoke City",1],["Hull City",3]],
[["Leeds United",3],["Watford",0]],
[["West Bromwich Albion",0],["Millwall",0]],
[["Swansea City",3],["Sheffield Wednesday",0]],
[["Rotherham United",1],["Preston North End",1]],
[["Plymouth Argyle",6],["Norwich City",2]],
[["Middlesbrough",2],["Southampton",1]],
[["Leicester City",1],["Bristol City",0]],
[["Ipswich Town",4],["Blackburn Rovers",3]],
[["Birmingham City",0],["Queens Park Rangers",0]],
[["Norwich City",0],["Leicester City",2]],
[["Watford",2],["West Bromwich Albion",2]],
[["Millwall",3],["Rotherham United",0]],
[["Hull City",0],["Leeds United",0]],
[["Huddersfield Town",2],["Stoke City",2]],
[["Blackburn Rovers",1],["Sunderland",3]],
[["Sheffield Wednesday",1],["Middlesbrough",1]],
[["Bristol City",4],["Plymouth Argyle",1]],
[["Southampton",0],["Ipswich Town",1]],
[["Queens Park Rangers",1],["Swansea City",1]],
[["Preston North End",2],["Birmingham City",1]],
[["Cardiff City",3],["Coventry City",2]],
[["Millwall",0],["Leeds United",3]],
[["Cardiff City",2],["Swansea City",0]],
[["Bristol City",0],["West Bromwich Albion",0]],
[["Blackburn Rovers",2],["Middlesbrough",1]],
[["Huddersfield Town",2],["Rotherham United",0]],
[["Sheffield Wednesday",0],["Ipswich Town",1]],
[["Norwich City",1],["Stoke City",0]],
[["Queens Park Rangers",1],["Sunderland",3]],
[["Watford",2],["Birmingham City",0]],
[["Preston North End",2],["Plymouth Argyle",1]],
[["Southampton",1],["Leicester City",4]],
[["Hull City",1],["Coventry City",1]],
[["Plymouth Argyle",3],["Blackburn Rovers",0]],
[["Ipswich Town",3],["Cardiff City",2]],
[["Leeds United",0],["Sheffield Wednesday",0]],
[["Leicester City",0],["Hull City",1]],
[["Middlesbrough",0],["Queens Park Rangers",2]],
[["Coventry City",3],["Watford",3]],
[["Rotherham United",2],["Norwich City",1]],
[["West Bromwich Albion",1],["Huddersfield Town",2]],
[["Stoke City",0],["Preston North End",2]],
[["Sunderland",5],["Southampton",0]],
[["Swansea City",1],["Bristol City",2]],
[["Birmingham City",1],["Millwall",1]],
[["Watford",0],["Blackburn Rovers",1]],
[["Ipswich Town",3],["Leeds United",4]],
[["Birmingham City",2],["Plymouth Argyle",1]],
[["Cardiff City",2],["Sheffield Wednesday",1]],
[["Coventry City",0],["Sunderland",0]],
[["Huddersfield Town",0],["Norwich City",4]],
[["Preston North End",2],["Swansea City",1]],
[["Millwall",1],["Stoke City",0]],
[["Rotherham United",1],["Leicester City",2]],
[["Southampton",2],["Queens Park Rangers",1]],
[["West Bromwich Albion",4],["Middlesbrough",2]],
[["Hull City",1],["Bristol City",1]],
[["Norwich City",3],["Millwall",1]],
[["Middlesbrough",1],["Huddersfield Town",1]],
[["Bristol City",0],["Birmingham City",2]],
[["Blackburn Rovers",1],["Hull City",2]],
[["Leicester City",2],["Cardiff City",1]],
[["Sunderland",2],["Rotherham United",1]],
[["Queens Park Rangers",0],["Ipswich Town",1]],
[["Stoke City",1],["Watford",0]],
[["Swansea City",1],["Coventry City",1]],
[["Sheffield Wednesday",0],["Preston North End",1]],
[["Plymouth Argyle",1],["Southampton",2]],
[["Leeds United",1],["West Bromwich Albion",1]],
[["Millwall",0],["Bristol City",1]],
[["Birmingham City",1],["Leeds United",0]],
[["Cardiff City",1],["Queens Park Rangers",2]],
[["Hull City",4],["Sheffield Wednesday",2]],
[["Ipswich Town",2],["Stoke City",0]],
[["Huddersfield Town",0],["Leicester City",1]],
[["Preston North End",2],["Sunderland",1]],
[["Southampton",4],["Norwich City",4]],
[["Watford",0],["Plymouth Argyle",0]],
[["West Bromwich Albion",3],["Swansea City",2]],
[["Rotherham United",2],["Blackburn Rovers",2]],
[["Coventry City",3],["Middlesbrough",0]],
[["Sunderland",1],["Ipswich Town",2]],
[["Leeds United",2],["Cardiff City",2]],
[["Leicester City",2],["Coventry City",1]],
[["Blackburn Rovers",2],["West Bromwich Albion",1]],
[["Watford",4],["Queens Park Rangers",0]],
[["Swansea City",1],["Birmingham City",1]],
[["Stoke City",4],["Rotherham United",1]],
[["Plymouth Argyle",3],["Huddersfield Town",1]],
[["Norwich City",2],["Hull City",1]],
[["Middlesbrough",0],["Millwall",1]],
[["Bristol City",1],["Preston North End",1]],
[["Sheffield Wednesday",1],["Southampton",2]]
]

Points, goal difference, goals for (don’t need to be output)

65 34 55 Leicester City
58 21 53 Southampton
58 16 50 Ipswich Town
54 24 50 Leeds United
45 13 40 West Bromwich Albion
43 13 43 Coventry City
42 4 42 Hull City
41 3 46 Norwich City
40 7 45 Watford
40 6 37 Sunderland
40 1 42 Middlesbrough
38 -12 34 Preston North End
37 0 31 Bristol City
37 -4 35 Cardiff City
33 0 47 Plymouth Argyle
33 -6 38 Swansea City
33 -12 41 Blackburn Rovers
32 -7 29 Millwall
32 -7 27 Stoke City
32 -10 34 Birmingham City
27 -18 28 Huddersfield Town
24 -15 24 Queens Park Rangers
22 -24 22 Sheffield Wednesday
19 -27 25 Rotherham United

Output for this example (from highest to lowest)

Leicester City
Southampton
Ipswich Town
Leeds United
West Bromwich Albion
Coventry City
Hull City
Norwich City
Watford
Sunderland
Middlesbrough
Preston North End
Bristol City
Cardiff City
Plymouth Argyle
Swansea City
Blackburn Rovers
Millwall
Stoke City
Birmingham City
Huddersfield Town
Queens Park Rangers
Sheffield Wednesday
Rotherham United

Alternative with integers for team names

[
[[9,2],[15,1]],
[[14,3],[4,1]],
[[11,1],[17,1]],
[[13,2],[24,0]],
[[20,1],[1,2]],
[[16,2],[12,0]],
[[18,1],[5,2]],
[[2,1],[6,1]],
[[3,1],[23,1]],
[[22,1],[19,3]],
[[21,0],[7,1]],
[[16,1],[23,2]],
[[8,2],[21,1]],
[[12,1],[11,3]],
[[17,0],[20,1]],
[[19,4],[18,0]],
[[24,4],[2,1]],
[[6,1],[14,1]],
[[4,0],[9,3]],
[[1,2],[22,2]],
[[15,2],[3,0]],
[[5,3],[10,1]],
[[7,1],[13,2]],
[[18,3],[7,1]],
[[13,1],[19,1]],
[[2,2],[17,2]],
[[3,0],[12,1]],
[[9,3],[1,0]],
[[10,4],[6,1]],
[[11,1],[5,3]],
[[14,3],[23,3]],
[[20,0],[8,0]],
[[22,1],[24,0]],
[[16,1],[4,2]],
[[21,2],[15,0]],
[[24,1],[9,0]],
[[8,0],[16,0]],
[[4,0],[10,2]],
[[5,2],[22,2]],
[[6,1],[11,2]],
[[7,3],[2,2]],
[[17,1],[21,1]],
[[12,1],[13,0]],
[[15,0],[18,1]],
[[23,1],[20,1]],
[[1,0],[3,0]],
[[19,2],[14,1]],
[[8,1],[10,1]],
[[1,1],[20,3]],
[[17,1],[11,0]],
[[19,5],[22,0]],
[[7,0],[21,1]],
[[6,3],[2,0]],
[[5,2],[18,0]],
[[4,2],[14,2]],
[[24,1],[13,0]],
[[23,1],[3,4]],
[[12,2],[16,0]],
[[15,2],[9,1]],
[[20,0],[12,0]],
[[21,0],[5,3]],
[[18,1],[4,2]],
[[10,3],[17,0]],
[[16,0],[19,1]],
[[14,3],[1,3]],
[[13,2],[6,0]],
[[11,1],[24,0]],
[[2,1],[23,2]],
[[9,4],[8,0]],
[[22,2],[15,1]],
[[3,3],[7,2]],
[[1,2],[10,3]],
[[24,1],[20,1]],
[[14,3],[17,2]],
[[22,1],[11,2]],
[[19,4],[2,0]],
[[18,2],[16,1]],
[[15,1],[23,5]],
[[12,1],[6,1]],
[[9,1],[5,1]],
[[7,3],[4,0]],
[[3,1],[21,0]],
[[8,2],[13,2]],
[[11,1],[7,2]],
[[4,0],[1,1]],
[[5,1],[19,1]],
[[13,3],[18,1]],
[[10,3],[12,2]],
[[16,0],[14,0]],
[[21,1],[9,0]],
[[23,1],[8,2]],
[[20,1],[22,1]],
[[17,0],[24,2]],
[[6,1],[15,3]],
[[2,2],[3,1]],
[[13,0],[15,0]],
[[4,1],[12,0]],
[[10,4],[14,0]],
[[11,0],[8,2]],
[[6,1],[3,1]],
[[16,2],[7,0]],
[[20,0],[18,1]],
[[23,1],[19,1]],
[[17,1],[22,2]],
[[21,2],[24,1]],
[[2,0],[9,2]],
[[5,2],[1,0]],
[[3,1],[13,2]],
[[12,1],[21,1]],
[[1,0],[17,0]],
[[7,1],[23,2]],
[[8,2],[5,1]],
[[9,3],[11,2]],
[[22,1],[6,1]],
[[14,2],[20,1]],
[[18,3],[2,1]],
[[19,2],[4,0]],
[[24,1],[10,2]],
[[15,0],[16,2]],
[[8,3],[12,1]],
[[2,4],[1,2]],
[[9,3],[22,1]],
[[18,1],[10,1]],
[[19,1],[3,0]],
[[21,1],[6,2]],
[[23,3],[13,2]],
[[16,4],[20,2]],
[[11,4],[15,0]],
[[7,4],[17,1]],
[[5,1],[14,0]],
[[4,0],[24,1]],
[[24,2],[8,0]],
[[12,0],[5,3]],
[[1,2],[18,1]],
[[3,3],[11,2]],
[[6,1],[19,1]],
[[10,2],[23,0]],
[[13,1],[16,0]],
[[15,1],[4,2]],
[[20,0],[2,3]],
[[22,2],[7,2]],
[[14,2],[21,0]],
[[17,1],[9,1]],
[[4,2],[13,3]],
[[9,2],[14,1]],
[[5,0],[20,0]],
[[7,1],[6,0]],
[[8,3],[22,2]],
[[19,2],[24,1]],
[[11,1],[10,0]],
[[16,0],[3,0]],
[[18,0],[12,4]],
[[23,5],[17,0]],
[[21,3],[1,1]],
[[2,1],[15,2]],
[[17,2],[8,2]],
[[13,1],[2,3]],
[[24,3],[7,1]],
[[22,0],[21,0]],
[[1,2],[8,2]],
[[3,1],[18,0]],
[[6,0],[23,0]],
[[17,1],[16,1]],
[[12,0],[19,1]],
[[14,3],[11,3]],
[[15,3],[5,2]],
[[20,0],[4,0]],
[[10,0],[9,1]],
[[5,0],[24,2]],
[[18,2],[17,0]],
[[8,3],[14,2]],
[[2,0],[22,1]],
[[4,2],[3,0]],
[[7,1],[15,0]],
[[11,0],[20,2]],
[[16,1],[10,2]],
[[21,3],[13,1]],
[[23,2],[12,2]],
[[9,4],[6,1]],
[[19,3],[1,1]],
[[20,1],[9,0]],
[[17,2],[5,0]],
[[15,2],[19,2]],
[[14,3],[18,0]],
[[3,0],[8,1]],
[[1,0],[7,2]],
[[24,2],[16,0]],
[[10,1],[21,0]],
[[22,0],[23,1]],
[[13,1],[11,2]],
[[12,1],[2,2]],
[[6,0],[4,4]],
[[11,1],[1,0]],
[[2,1],[4,0]],
[[3,1],[5,0]],
[[6,2],[16,1]],
[[7,1],[19,2]],
[[24,0],[14,0]],
[[13,2],[9,3]],
[[20,2],[21,1]],
[[22,1],[10,3]],
[[23,1],[18,0]],
[[15,1],[12,1]],
[[4,1],[23,1]],
[[19,1],[17,1]],
[[18,0],[6,0]],
[[16,0],[2,4]],
[[14,1],[22,3]],
[[12,2],[7,2]],
[[10,2],[20,0]],
[[9,2],[3,1]],
[[8,4],[15,2]],
[[5,1],[13,1]],
[[21,0],[11,4]],
[[1,3],[24,1]],
[[17,1],[3,2]],
[[21,2],[23,0]],
[[10,3],[15,0]],
[[9,1],[16,0]],
[[5,1],[2,0]],
[[22,2],[13,1]],
[[24,1],[18,0]],
[[20,0],[19,1]],
[[14,0],[12,2]],
[[11,2],[4,0]],
[[8,3],[7,0]],
[[1,4],[6,1]],
[[2,1],[10,4]],
[[6,1],[8,1]],
[[12,0],[22,3]],
[[4,2],[17,0]],
[[3,2],[20,3]],
[[7,1],[14,1]],
[[13,2],[1,0]],
[[16,1],[5,3]],
[[23,2],[11,3]],
[[15,0],[24,4]],
[[19,3],[9,1]],
[[18,0],[21,3]],
[[5,1],[6,1]],
[[21,0],[4,1]],
[[20,1],[7,3]],
[[9,3],[23,0]],
[[24,0],[12,0]],
[[22,3],[18,0]],
[[17,1],[15,1]],
[[14,6],[13,2]],
[[11,2],[19,1]],
[[10,1],[3,0]],
[[8,4],[2,3]],
[[1,0],[16,0]],
[[13,0],[10,2]],
[[23,2],[24,2]],
[[12,3],[17,0]],
[[7,0],[9,0]],
[[6,2],[20,2]],
[[2,1],[21,3]],
[[18,1],[11,1]],
[[3,4],[14,1]],
[[19,0],[8,1]],
[[16,1],[22,1]],
[[15,2],[1,1]],
[[4,3],[5,2]],
[[12,0],[9,3]],
[[4,2],[22,0]],
[[3,0],[24,0]],
[[2,2],[11,1]],
[[6,2],[17,0]],
[[18,0],[8,1]],
[[13,1],[20,0]],
[[16,1],[21,3]],
[[23,2],[1,0]],
[[15,2],[14,1]],
[[19,1],[10,4]],
[[7,1],[5,1]],
[[14,3],[2,0]],
[[8,3],[4,2]],
[[9,0],[18,0]],
[[10,0],[7,1]],
[[11,0],[16,2]],
[[5,3],[23,3]],
[[17,2],[13,1]],
[[24,1],[6,2]],
[[20,0],[15,2]],
[[21,5],[19,0]],
[[22,1],[3,2]],
[[1,1],[12,1]],
[[23,0],[2,1]],
[[8,3],[9,4]],
[[1,2],[14,1]],
[[4,2],[18,1]],
[[5,0],[21,0]],
[[6,0],[13,4]],
[[15,2],[22,1]],
[[12,1],[20,0]],
[[17,1],[10,2]],
[[19,2],[16,1]],
[[24,4],[11,2]],
[[7,1],[3,1]],
[[13,3],[12,1]],
[[11,1],[6,1]],
[[3,0],[1,2]],
[[2,1],[7,2]],
[[10,2],[4,1]],
[[21,2],[17,1]],
[[16,0],[8,1]],
[[20,1],[23,0]],
[[22,1],[5,1]],
[[18,0],[15,1]],
[[14,1],[19,2]],
[[9,1],[24,1]],
[[12,0],[3,1]],
[[1,1],[9,0]],
[[4,1],[16,2]],
[[7,4],[18,2]],
[[8,2],[20,0]],
[[6,0],[10,1]],
[[15,2],[21,1]],
[[19,4],[13,4]],
[[23,0],[14,0]],
[[24,3],[22,2]],
[[17,2],[2,2]],
[[5,3],[11,0]],
[[21,1],[8,2]],
[[9,2],[4,2]],
[[10,2],[5,1]],
[[2,2],[24,1]],
[[23,4],[16,0]],
[[22,1],[1,1]],
[[20,4],[17,1]],
[[14,3],[6,1]],
[[13,2],[7,1]],
[[11,0],[12,1]],
[[3,1],[15,1]],
[[18,1],[19,2]]
]

Shorter examples

All are given as [[first team, first team score],[second team, second team score]] but this order can be transposed if preferred.

[[1,1],[2,1]],[[2,2],[1,0]] -> 2,1
[[1,2],[2,3]],[[1,2],[3,2]],[[1,3],[4,1]],[[1,2],[5,1]],[[2,2],[3,4]],[[2,4],[4,2]],[[2,2],[5,2]],[[3,4],[4,2]],[[3,3],[5,2]],[[4,4],[5,2]],[[2,4],[1,2]],[[3,3],[1,3]],[[4,2],[1,3]],[[5,1],[1,2]],[[3,3],[2,3]],[[4,2],[2,3]],[[5,3],[2,1]],[[4,3],[3,1]],[[5,3],[3,2]],[[5,1],[4,3]] -> 2,1,3,4,5
[[1,3],[2,4]],[[1,3],[3,3]],[[2,0],[3,2]],[[2,3],[1,1]],[[3,4],[1,0]],[[3,3],[2,2]] -> 3,2,1
[[1,3],[2,2]],[[1,3],[3,1]],[[1,4],[4,0]],[[2,2],[3,2]],[[2,3],[4,3]],[[3,2],[4,1]],[[2,3],[1,2]],[[3,3],[1,4]],[[4,2],[1,2]],[[3,4],[2,1]],[[4,2],[2,2]],[[4,4],[3,2]] -> 1,3,2,4
[[1,0],[2,2]],[[1,2],[3,0]],[[1,2],[4,0]],[[2,1],[3,2]],[[2,2],[4,4]],[[3,3],[4,2]],[[2,4],[1,3]],[[3,2],[1,2]],[[4,3],[1,2]],[[3,2],[2,3]],[[4,2],[2,2]],[[4,4],[3,2]] -> 4,2,1,3

Questions

  1. The hardest bit seems to be checking head to head record. That’s in the rules, but does it over-complicate things?
  2. Are the examples, particularly the real-world one, too long?
\$\endgroup\$
0
\$\begingroup\$

How many ways does this string conform to this expression?

Given an expression, decide in how many ways could an inputted string consisting of only printable ascii conforms to that expression. The best way to explain how the expression works is with an example, so here is one.

Let's say the expression is a + b + c + a. That means the string should start with a contiguous substring a, then at some point split into substring b, and finally end with substring a again (is this example, a, b, and c must be distinct.) Now let's say the string is "hello world please subscribe hello". One possible way would be:

a = "hello"
b = " world "
c = " please subscribe "

You task is to find how many ways you can split up the string so that the resulting substrings conform to the expression. If no split exists, output/return 0.

[more coming soon]

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

Tile the untileable

Only triangles, squares, and hexagons can tile perfectly with no gaps. With any other polygon, there will always be gaps. But what if you could tile with say, a pentagon? You just have to cheat, with other shapes. Given two integers a and b, how many x-sided polygons where a != x and x >= 3 are needed so that you can tile b a-sided polygons perfectly with the help of x-sided polygons? You may assume it is always possible.

More constraints

  • The area and perimeter of all a-sided polygons must be equal
  • ^ must also hold for the n x-sided polygons

[example and test cases coming soon]


  • I don't know how to do this at all.
  • The wording could probably be better.
\$\endgroup\$
1
  • \$\begingroup\$ "Only triangles, squares, and hexagons can tile perfectly with no gaps" You should have the word "regular" somewhere, otherwise this is wrong and sort of confusing. It's overall not clear to me what polygons are assumed to be regular in this question. \$\endgroup\$
    – Wheat Wizard Mod
    Jan 30 at 5:28
0
\$\begingroup\$

Solve a squared cryptarithm

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

Summarise a Long Conversation


Note: I'm aware that there's been some attempts at doing chatgpt golf on the site but there's always been the problem of subjectivity. I've come up with an idea that could maybe add objectivity to the concept of general LLM golfing

Second note: prompt golf doesn't exist as a tag yet so it'd be created upon question posting most likely if at all

Final note: this might be better as a meta discussion, but just to kick things off I've made it a sandbox post


Inspired by a real life problem

If you ever been in a busy SE chat room/discord server/whatsapp group chat or any other place where you can talk over the internet and there's lots of messages, you'll know that it can be hard to keep up with what's being discussed. Especially if you've been away for a while (e.g sleep) and there's literal hundreds of new messages.

Your task today is to take a list of messages and summarise it into a nice digestible format.

"But that's a hard problem people have spent years researching and everything like how do you expect us to write a summarisation algorithm that's actually good without using something like a LLM?"

By using a LLM, obviously.

Challenge

Given a series of messages with each individual message on a new line, write a prompt that summarises the content.

To verify that the output is actually a summary, the result will be run by an oracle prompt in <insert LLM that'll be used for testing>:

<prompt I've yet to write that outputs either yes or no depending on whether the oracle LLM would summarise in the same way>

To account for the non-deterministic behaviour of LLMs (their temperature), your prompt must return an accepted result for at least 4 out of 5 runs. required run rate subject to change. This is to establish that it's a genuinely working prompt and not a fluke.

Alternatively, if your LLM has a temperature setting you can set to 0, or is deterministic by default only one verified run is needed.

Input Format

name: message
name: message

Rules

to be finalised - I might decide to switch up how this challenge is scored

  • Inputs will not be longer than 1000 characters (to ensure no token limits are reached)
  • Prompts that try to return results that jailbreak the oracle are allowed, but note that you'll probably find better results by just doing the task legitimately.
  • LLMs you can use are Chatgpt 3.5/ 4 and Google Bard.
  • provide links to sample runs if possible.
  • The answer(s) with the shortest prompt as measured in utf-8 bytes wins.

Example Inputs

todo

Sandbox meta

  • Does this work towards solving the subjectivity problem of prompt golf?
  • Does the testing/verification method need more runs or a different set-up?
  • Is prompt golf even something that should be a challenge?
  • Are there any other things I haven't thought of?
\$\endgroup\$
3
  • \$\begingroup\$ So basically, you are given a transcript and give a prompt to an LLM to summarize the transcript, right? How do you compare how good summarizations are? \$\endgroup\$ Jan 30 at 13:11
  • \$\begingroup\$ @AlanBreadel that's what the Oracle LLM is for. It's used to determine whether an output is valid. \$\endgroup\$
    – lyxal
    Jan 30 at 13:41
  • \$\begingroup\$ How do you make sure the Oracle LLM isn't biased? (for example the oracle gives a higher score to prompts that praise it) \$\endgroup\$ Jan 30 at 14:53
0
\$\begingroup\$

bit-packing

The GSM7 03.38 protocol specifies a bit packing/unpacking algorithm, to pack septets into octets and vice-versa.

The following https://www.codeproject.com/Tips/470755/Encoding-Decoding-7-bit-User-Data-for-SMS-PDU-PDU is a reasonable reference implementation, which details the packing algorithm.

challenge

the packing algorithm - shortest code wins.

input

byte array in a style relevant to your language

output

packed byte array

You can use http://smstools3.kekekasvi.com/topic.php?id=288 to check your work - enter some text at the top, click convert, convert again, and then "User data translation (7 bit only)" for a handy comparison chart between the octets and septets.

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

The TAK function (easy mode)

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

Modular Equivalence

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

3D Hide & Seek Word Puzzle

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

Solve a logic puzzle by exhaustively applying three rules to rows and columns of a table

\$\endgroup\$
1
  • \$\begingroup\$ @noodleman Thanks for your feedback on my original post. Are the examples in this post clear enough? \$\endgroup\$
    – oldsoul
    Feb 4 at 1:03
0
\$\begingroup\$

Alternating Random Series Sum To \$N\$

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

Counting rankings

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

State compression


A long time ago in a challenge far, far away, golfers were tasked with outputting one of three different outputs, depending on whether the input was: OR, one of the other 49 American states' two-letter abbreviations, or something else entirely. The list of these letter pairs looks like this:

AL, AK, AZ, AR, CA, CO, CT, DE, FL, GA, HI, ID, IL, IN, IA, KS, KY, LA, ME, MD, MA, MI, MN, MS, MO, MT, NE, NV, NH, NJ, NM, NY, NC, ND, OH, OK, OR, PA, RI, SC, SD, TN, TX, UT, VT, VA, WA, WV, WI, WY

The standard approach to achieve the task was to search for the input in this string, bar the commas but not the spaces. If the spaces were to be removed, unintended letter pairs would appear within the string. For example, this string would start with ALAKAZ and while the newly formed LA is one of the valid pairs (and hence, did not need to appear again in the search string), the same cannot be said for KA. (And you'd probably anger some people from Kansas. I dunno, I've no idea what people from Kansas get up to.)

But, with some careful rearrangement, the technique could be used in certain places to save a handful of bytes. The string that most solutions ended up using looked like this:

MINCALA MSCTNMNVAKY WAZ PAR FL GA NHID COKSD ME MDE MA MTX NE NJ NY ND MOH ORIA UT WVT WIL WY

Pretty unrecognizable, right? If you look at the first "word", MINCALA, it contains MI, IN, NC, CA, AL, and LA, which are all valid pairs. But if you were to remove the space after it, then you would end up with AM, which is not a valid pair.

Thing is though, I'm still not entirely certain this string is optimal, which is why I'm asking you to...

Challenge

Write a program/function that takes a list of strings of uniform length and outputs the shortest list of combinations that, when combined into a string with some delimiter, contains all the input strings, but no other string of the same length without that delimiter.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, unless otherwise specified.
  • Built-in functions that achieve this (now that's unlikely) are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

Yet to come.

This challenge was sandboxed.


Sandbox

  • This title still sucks.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is it allowed for a string to appear multiple times in the search string? I'm not sure how this could work with nonuniform lengths. What do you mean by a decision-problem? Testing if a given search string is valid? This seems very different, and IMO this question is more interesting. \$\endgroup\$ Feb 3 at 17:47
  • \$\begingroup\$ @CommandMaster I'm not against strings appearing multiple times in the output inherently but I don't know if that can happen in the optimal output. As for the kind of challenge it is, I have decided it'll be a code-golf. \$\endgroup\$ Feb 7 at 12:10
  • \$\begingroup\$ A typical solution may works in \$O((n+1)!k)\$ where \$n\$ is the number of candidate strings and \$k\$ is the size of strings. As the result, it could probably cannot handle any large testcases. \$\endgroup\$
    – tsh
    Mar 6 at 11:17
  • \$\begingroup\$ Maybe testcase "EAB ABC BCA CAB BCE" -> "EABCABCE" use "ABC" twice \$\endgroup\$
    – tsh
    Mar 6 at 11:20
0
\$\begingroup\$

Generate a sequence of \$n\$ consecutive composite numbers

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

TYPOGLYCEMIA - Cna Yuo Raed Tihs?

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

NDos' Well-Temperament

Objective

Given a positive integer \$n\$, output the ratios in the NDos' well-temperament with \$n\$ notes, as defined below.

NDos' well-temperament

NDos' well-temperament (abbr. NWT) is a musical temperament whose every step is a superparticular ratio. A ratio is superparticular if it equals \$\frac{n+1}{n}\$ for some positive integer \$n\$.

By being octave-periodic, NWT with \$n\$ notes is essentially a multiplicative partition of the rational number \$2\$ with \$n\$ entries.

There is one restriction that ensures NWT to exist uniquely. Amongst such multiplicative partitions, NWT is the partition that comes the last co-lexicographically (That is, the last ratio must be the biggest as possible, the second-to-last ratio is a tiebreaker, the third-to-last ratio is another tiebreaker, and so on) when the ratios are sorted in descending order.

I/O format

Flexible. In particular, since the outputted list consists of superparticular ratios, you can output their denominators only, or output their numerators only. Note that, by doing this, NWT becomes the first partition in co-lexicographic order when the denominators (or the numerators) are sorted in ascending order.

Notes

Musically, NWT will sound better if its ratios are rearranged in a particular way. This challenge won't ask to rearrange them.

Examples

Only denominators are shown for the ratios.

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

Ungolfed solution (Haskell)

This particular implementation is quite slow upon bigger inputs. Haven't analyzed the time complexity exactly, but I doubt this runs in polynomial time.

import Data.List

colex :: Ord a => [a] -> [a] -> Ordering
colex [] [] = EQ
colex [] _  = LT
colex _  [] = GT
colex (x:xs) (y:ys) = colex xs ys <> compare x y

ndosWT :: Int -> [Int]
ndosWT = go [1] where
    go :: [Int] -> Int -> [Int]
    go [] _ = []
    go [x] 1 = [x]
    go [x] n = minimumBy colex $ do
        m <- [2 .. n]
        let ys = take m [m*x ..]
        pure (go ys n)
    go xs@(x:xs1) n = case compare n (length xs) of
        LT -> []
        EQ -> xs
        _  -> minimumBy colex $ do
            m <- [quot (n + (length xs - 1)) (length xs) .. n - (length xs - 1)]
            pure (sort (go [x] m ++ go xs1 (n-m)))

Optimized version:

import Data.List
import Data.Maybe

colex :: Ord a => [a] -> [a] -> Ordering
colex [] [] = EQ
colex [] _  = LT
colex _  [] = GT
colex (x:xs) (y:ys) = colex xs ys <> compare x y

ndosWT :: Int -> [Int]
ndosWT n = fromJust (go [1] n)
  where
    threshold :: Int
    threshold = 2 * n

    colex_maybe_min :: Ord a => Maybe [a] -> Maybe [a] -> Maybe [a]
    colex_maybe_min Nothing mys = mys
    colex_maybe_min mxs Nothing = mxs
    colex_maybe_min (Just xs) (Just ys) = if GT == colex xs ys
        then Just ys
        else Just xs

    weave :: Ord a => [a] -> [a] -> [a]
    weave [] ys = ys
    weave xs [] = xs
    weave xs@(x:xs1) ys@(y:ys1) = if x <= y
        then x : weave xs1 ys
        else y : weave xs ys1

    go :: [Int] -> Int -> Maybe [Int]
    go [] _ = Nothing
    go [x] 1 = if x < threshold
        then Nothing
        else Just [x]
    go [x] n = foldr1 colex_maybe_min $ do
        m <- [2 .. n]
        let ys = take m [m*x ..]
        pure $ if last ys < threshold
            then go ys n
            else Nothing
    go xs@(x:xs1) n = case compare n (length xs) of
        LT -> Nothing
        EQ -> Just xs
        _  -> foldr1 colex_maybe_min $ do
            m <- [quot (n + (length xs - 1)) (length xs) .. n - (length xs - 1)]
            pure (fmap (\[xs, ys] -> weave xs ys) (sequence [go [x] m, go xs1 (n-m)]))
\$\endgroup\$
0
\$\begingroup\$

String to Lojban!

In the constructed language Lojban, you can express ASCII strings with a literal quote, for example
zoi zoi \d+(\.?\d+) zoi. However, how would you pronounce that?

zoi zoi backslash d plus opening bracket backspash dot question mark 
backslash d plus closing bracket zoi

? Non-English speakers won't understand you. However, there are several ways to assign Lojban words or phrases to ASCII characters. One is shown in the challenge.

So here is the challenge:

The input is a string. You can assume it is composed of only the 95 printable ASCII characters.

The output is a Lojban representation of the string. It should start with me'o , followed by the following substrings in order:

SP -> canlu bu
!  -> saibu
"  -> lubu
#  -> libu
$  -> meryru'u bu
%  -> ce'obu
'  -> y'y
&  -> joibu
(  -> tobu
)  -> toibu
*  -> pi'ibu
+  -> su'ibu
,  -> slaka bu
-  -> vu'ubu
.  -> denpa bu
/  -> fe'ibu
0  -> no
1  -> pa
2  -> re
3  -> ci
4  -> vo
5  -> mu
6  -> xa
7  -> ze
8  -> bi
9  -> so
:  -> zo'ubu
;  -> pi'ebu
<  -> me'ibu
=  -> dubu
>  -> za'ubu
?  -> paubu
@  -> zvati bu
[  -> veibu
\  -> lu'ebu
]  -> ve'obu
^  -> te'abu
_  -> dizlo bu
{  -> lu'ibu
|  -> jabu
}  -> lu'ubu
~  -> nabu

This is a modification of an existing system which can represent all 95 printable ASCII characters.

For lowercase letters, just add y after the letter, with these exceptions:

a  -> abu
e  -> ebu
h  -> y'y bu
i  -> ibu
o  -> obu
q  -> ky bu
u  -> ubu
w  -> vy bu

You can also use tau y'y for h.

For uppercase letters, use tau followed by the corresponding lowercase letter, however h must be
tau y'y bu.

After that, the substrings are joined with a single space, however for readability, no spaces are used between digits.

However, if the string is empty, output lo kutyuenzi.

Examples:

Input -> Output
1 2 -> me'o pa canlu bu re
Hello -> me'o tau y'y bu ebu ly ly obu
1234 -> me'o parecivo
12>1 -> me'o pare za'ubu pa
\d+(\.?\d+) -> me'o lu'ebu dy su'ibu tobu lu'ebu denpa bu paubu lu'ebu dy su'ibu toibu
 -> lo kutyuenzi

This is code-golf, so shortest answer in bytes wins.

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

Spot The Difference

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

Infinite monkeys with autocomplete

You've probably heard of the infinite monkey theorem, which states that a monkey pressing keys on a keyboard at random will eventually type any possible string, the most well-known example being the complete works of Shakespeare. Of course, as the string grows longer and longer, the time taken to type that string becomes exponentially longer. But what if the monkey had an autocomplete?

Our hypothetical monkey starts with an alphabet, containing every possible character that it can type, and a dictionary that initially only contains every letter in the alphabet. At every step, it'll choose a random item from the dictionary and type it. But, the monkey has a helpful autocomplete guiding it to the correct string - if the last two items that were typed, concatenated, are a substring of the correct word that's not yet in the dictionary, it'll add that substring to the dictionary.

For example, let's start with the monkey trying to type the word hello, with the alphabet helo.

l o

It first types l and o and adds lo to the dictionary.

l o h lo l h e

It then types various random dictionary items before typing h and e, and adding he to the dictionary.

l o h lo l h e e e l

After some more random items, it types e and l and adds l to the dictionary.

l o h lo l h e e e l h lo o el e h el

Next, it types h and el and adds hel.

l o h lo l h e e e l h lo o el e h el lo

After typing the el, it types lo and adds ello to the dictionary.

l o h lo l h e e e l h lo o el e h el lo he hel he l o

Next, it types he and l, but because hel is already in the dictionary it's not added. For the same reason, lo is also not added.

l o h lo l h e e e l h lo o el e h el lo he hel he l o h ello

Finally, it types h and ello, creating hello after 24 attempts.

Your challenge is to, given a target word and alphabet containing only lowercase ASCII letters and spaces, simulate this behaviour, choosing random items and building up the dictionary until you eventually create the desired word. The alphabet will not contain any character more than once, and will at least contain every character in the target word.

At every step, you should choose a (not necessarily uniformly) random item from the dictionary, and the words you print should be separated by some consistent and unambigiuous delimiter. Although you do not have to uniformly randomly choose an item, it should be possible for any possible output sequence of strings to occur.

This is , shortest wins!

Examples

Note that this is just one possible output for each input.


word = "abcba", alphabet = "abc" -> "a,a,c,b,b,cb,c,bcb,bcb,a,a,b,cb,ab,cb,b,bcba,bcba,c,b,cb,c,ab,bcba,c,bcb,ab,c,bcba,bcb,bcb,b,bcb,bcba,ab,a,b,a,c,cb,c,bcba,cb,abcb,abcb,ba,ba,abc,a,b,bcb,ab,bcb,a,ba,b,bcb,abc,c,abcb,a"
word = "hello", alphabet = "helo" -> "o,l,h,o,e,e,h,l,e,o,l,o,lo,lo,l,e,h,h,o,lo,h,l,lo,h,o,llo,o,llo,e,o,llo,lo,l,e,e,o,e,o,lo,l,l,ll,llo,h,l,ll,e,h,e,l,he,llo"
word = "hello", alphabet = "abcdefghijklmnopqrstuvwxyz" ->
"k,p,o,d,t,s,c,e,j,b,n,f,h,u,k,b,z,q,f,j,m,e,h,y,m,k,f,q,o,r,q,m,y,o,a,w,b,j,r,d,q,u,k,m,b,j,c,p,p,i,e,h,a,y,l,q,a,k,b,s,l,g,t,f,v,w,c,l,p,b,n,u,h,b,u,e,r,g,u,f,x,b,x,j,p,q,p,i,e,n,x,o,y,u,b,l,b,z,z,x,w,d,p,q,p,i,h,c,i,h,m,j,q,b,b,v,d,e,b,f,f,u,q,z,d,r,a,q,p,v,t,z,o,c,z,c,t,u,n,q,l,i,a,t,f,j,a,d,g,h,s,l,t,v,l,a,t,z,i,l,j,z,x,t,q,o,a,v,q,t,p,e,d,n,p,t,i,d,c,o,r,k,y,t,b,s,l,c,w,l,a,o,y,k,e,u,r,v,t,f,f,e,f,m,v,r,a,k,b,q,q,a,l,y,u,u,m,c,e,l,m,q,b,u,r,n,m,n,f,j,t,s,n,b,t,q,el,b,el,w,d,g,w,c,h,h,x,p,o,q,o,y,r,p,t,t,p,o,j,h,d,g,q,z,d,s,b,g,i,f,g,d,v,w,k,c,u,h,w,c,z,r,el,w,y,b,s,j,l,i,v,o,q,h,l,t,j,n,u,h,p,b,t,s,g,h,i,b,o,r,g,o,q,w,z,p,t,p,k,x,a,g,x,h,k,u,h,a,h,v,b,n,e,u,f,d,k,m,h,e,d,d,c,j,el,i,u,b,n,f,d,x,t,j,t,c,d,j,r,v,r,i,k,d,m,z,n,h,x,p,e,t,q,q,a,b,u,y,r,j,v,l,f,k,el,m,he,c,a,j,r,r,b,he,g,z,t,c,y,x,b,u,i,j,j,x,b,d,he,he,l,g,t,o,v,o,e,f,o,u,j,e,g,z,h,t,i,w,c,a,m,m,i,n,g,t,u,t,q,m,n,c,y,o,t,h,i,h,w,l,t,p,h,i,g,t,he,f,x,n,k,d,g,p,i,w,p,r,g,j,r,e,he,h,t,v,x,e,el,n,e,r,n,y,v,r,f,o,w,d,y,g,n,hel,c,he,k,x,q,k,q,h,l,d,l,he,i,w,h,l,b,k,y,k,h,e,s,s,g,y,x,n,p,c,k,l,he,l,g,k,s,hel,f,a,el,s,w,w,s,h,d,o,w,x,p,el,q,o,b,j,h,p,i,o,j,v,n,q,q,he,d,y,l,s,w,he,v,w,k,a,hel,b,h,t,a,u,s,s,x,y,b,p,d,e,l,y,m,x,w,s,t,hel,m,hel,x,h,p,c,u,h,q,a,i,hel,i,j,hel,x,hel,a,q,el,z,x,m,z,e,t,a,e,z,s,l,j,u,x,q,h,a,c,k,h,y,c,y,a,j,h,m,d,hel,r,q,v,a,f,el,v,p,i,el,c,n,p,a,r,o,s,o,a,hel,c,i,h,he,g,x,j,f,g,c,v,a,he,q,i,e,f,r,y,w,g,e,u,i,q,f,v,o,m,hel,c,u,h,d,o,p,y,s,p,he,el,v,hel,z,he,f,z,h,h,c,r,p,c,p,j,v,z,m,f,y,k,n,a,u,l,x,t,d,v,x,el,hel,e,i,p,c,n,hel,z,k,p,j,d,c,el,y,e,t,h,h,f,e,a,f,w,h,hel,e,el,n,el,m,l,x,t,el,o,t,n,t,o,h,el,c,x,v,hel,j,v,t,i,i,c,hel,p,t,h,z,q,p,w,h,w,x,u,k,q,b,e,w,q,j,s,y,b,i,h,a,c,q,g,hel,hel,l,he,b,d,y,m,hel,v,i,m,l,h,e,j,z,t,x,hell,k,m,y,v,d,n,s,hell,c,x,hel,a,u,hel,f,e,v,hel,c,hel,f,e,j,k,hel,y,x,t,e,hel,j,h,d,u,h,i,h,s,i,c,w,d,he,n,t,y,hel,he,m,hell,x,n,n,x,c,c,i,he,hel,b,j,j,y,v,a,a,g,n,he,v,r,i,p,c,o,r,t,s,hel,hel,y,l,y,e,r,g,b,h,he,el,u,q,i,hel,b,hel,i,w,m,u,q,j,c,b,j,l,s,w,o,s,u,s,c,l,el,s,d,o,q,j,j,e,hell,c,m,x,a,he,n,q,v,s,u,hell,n,e,n,c,x,m,v,v,z,v,b,h,f,o,u,m,l,h,he,el,n,el,b,z,a,o,w,l,i,j,el,n,f,i,e,p,m,c,hel,p,b,j,k,e,u,y,he,v,e,h,i,x,j,o,f,j,o,o,hell,q,d,n,m,j,n,a,a,el,n,b,n,y,a,t,y,f,f,l,p,c,w,el,g,el,hel,j,d,n,he,he,z,a,e,c,w,b,e,el,b,x,n,a,a,x,y,a,hel,a,hell,he,g,g,c,q,l,z,o,x,y,h,r,o,he,q,x,q,x,hell,a,l,o,e,l,k,l,m,w,lo,he,x,l,l,x,o,z,j,i,b,d,g,h,he,i,el,q,l,k,k,a,hel,ll,h,z,m,b,m,j,y,ll,s,v,u,ll,ll,f,f,p,p,m,d,g,g,lo,e,l,w,el,s,el,k,r,c,u,g,hell,o"
word = "hello world", alphabet = "abcdefghijklmnopqrstuvwxyz" -> " ,k,l,q,x,w,d, ,a,o,b,v,h,n,n,i,l,f,u,t,u,n, ,g,j,s,t,i,g,d,f,g,b, ,o,f,t,x,d,q,w,k,d,t,n,d,v,h,e,m,he,s,b,h,w,l,h,x,e,j,o,g,i,f,f,c,h,k,a,y,z,r,j,l,v,k,i,he,p,x, ,f,u,m,d,p,c,s,p,y,e,k,w,u,q,f,f,s,f,f,a,z,w,l,e,v,q,a,r,y,l,u,he,x,z,z, ,k,k,k,i,u,m,q,k,t, ,l,k,he,y, ,z,l,he,x,x,w,n,w, ,l,v,c,o,h,g,e,b,n,q,j,a,c,p,j,he,p,r,w,c,s,l,j,g,j,x,y,i,c, ,q,c,i,j,v,s,r,a,z,c,d,m,f,w,i,z,a,s,t,l,he,a,r,r,he,a, ,v,q,o,r,y,b,n,j,k,d,m,i,t,b,v,q,y, ,y,l,he,r,or,r,t,b, ,a,q,z,h,l,e,w,y,l,t,o,or,d,l,j,h,g,e,h,y,g, ,x,k,g,he,b,r,or,he,he,g,m,t,he,s,j,c,d,v,l,he,e,a, ,or,h,h,g,or,j,u,l,f,o, ,p,k,z,g,q,u,h,j,k,o , ,r,he,o ,e, ,g,x,o,v,b,t,f,q,d,w,p,o,u,j,c,q, ,t,k,q,or,a,he,h,g,v,t,j,g,or,x,h,t,s,t,i,he,d,q,y,t,d,b,d,o ,g,l,l,he,n,e,v,y,x,or,y,g,he,p,k, ,x,d,c,o ,n,o ,or,s,v,q,o ,g,n,he,o,m,o,u,d,z,he,n,o,t,r,p,n,g,g,w,m,o ,b,h,s,or,or,a,n,m,z,r,u,e,i,h,m,v,g,o,g,f,k,p,j,t,v,d,k,c,m,h,x,z,f,f,d,e,o,h,a,m,b,or,ll,k,m,b,e,f,y,or,l,u,v,x,u,h,x,n,p,orl,p,k,p,b,y,x,x, ,a,a,he,a,i,h,d,x,w,or,j,w,wor,ll,h,x,orl,f,j,b, ,c,z,h,z,q,s,h,n,u,he,k,v,x,orl,w,u,r,m,h,g,p,b,j,a,g,i,h,b,d,r,a,k,i,orl,he,l,l,t,ll,or,o,q,ll,j,q,d,h,k,o,n,d,k,e,x,a,d,h,p,c,h,f,i,x,i,e,p,hel,o,he,or,r,s,e,g,j,u,v,v,f, ,e,y,o,u,ll,hel,f,c,n,v,x,f,h,w,x,b,o ,r,h,k,a,x,g,f,s,o,s, ,a,orl,l,v,o ,d,i,orl,x,e,wor,orl,hel,v,wor,f,l,t,j,i,f,w,o ,e,c,y,f,z,v,t,hel,or,s,n,y,g,w,hel,c,v,x,i,j,f,o,j,z,a,p,ll,x,m,e,r,o ,g,q,f,i,j,b,y,v,b,q,e,o ,y,orl,g,v,wor,p,wor,w,d,s,o ,k,h,t,or,a,v,r,p,s,i,t,y,g,l,z,y,a,u,f,c,p,p,b,orl,h,a,g,x,g,s,n,f,x,u,s,b,i,wor,orl,r,orl,f,ll,or,hel,wor,d,d,a,x,hel,o,hel,e,m,wor,f,e,k,x,a,d,p,o ,k,orl,m,m,hel,z,g,j,c,f,j,u,ll,h,d,e, ,t,j,c,f,wor,he,p,orl,d,r,orl,hel,q,b,b,wor,y,p,u,he,z,b,he,h,s,ll,y,wor,a,t,b,c,z,y,y,v,b,o ,d,b,or,s,d,k,q,l,x,b,p,orl,e,x,wor,ll,orl,y,o,l, ,a,g, ,x,d,e,wor,y,t,w,orl,c,f,s,i,c,hel,z,i,w,hel,f,i,y,ll,e,x,g,orld,wor,he,n,c,or,x,ll,ll,s,l,t,ll,l,p,q, ,w,worl,a,q,he,i,x,l,hel,g,o , w,m,c,o ,l,z,worl,j,i,y,n,b, w,b,wor,f,r,u,j,l,u,f,z,z,m,c,orld,c,e, w,ll,m,x,y,u,j,t,hel,o ,b,wor,he,m,d,n,f,orld,or,u,i,i,e,c,q,b,t, w,p,c,t,orl,p,c,o ,q,hel,w,orld,c,e, w,orl,b,r,u,y,ll,g,wor,hel,n,s,d,g,y,j,b,t,q,wor,hel,hel,s,y,b,a,or,n,h,orld,hel,orl,k,ll, ,f,z,o ,u,o, worl,he,o,v,e,or,r,wor,wor, worl,h,he,q,c,q,hel,orld,or,u,p,v,hel,ll,or,x,he,o ,q,ll,he,d,x,o ,orl,o ,z,o,b,world,g,or,s,v,a,o ,r,f,hel,i,r,c,s,q,ll,s,u,h,n,u, w,or,u,world,v,m,w,l,x,wor,o ,n,x, wor,a,g,orl,c, ,n,l,o ,w,k,orld,a,w,x, w,g,hel, ,k,orl,orl,r,v,l,o,o,j,orl,o worl,r,s,worl,wor,l,v,o , worl,z,n,lo ,orl,or,s,hel,world,orl,c,u,hel,z,n,z,c,orl,o w,worl,he,e,b,h,f,u,w,k,orl, wor,k,wor,c,f,orl,o worl,f,y,lo ,x,v,l,o ,c,c,z,lo,a,u,hel,orld,world, worl,orl,y,k,ll,ll,e, wor,d,h,j,a,he,j,orl, w,s, wor,he,j,orld,worl,k,hel,u,b,hel,r,w,hel,g,hel,lo, w,o worl,lo ,w,world,o ,lo w,b,t,l,b,u,q,hello, worl,or,p,hello worl,u, ,o ,o w,hel,or,or,u,z, , ,h,hello,o ,z,t,k,q,b,o w,t,m,he,m,w,worl,t,p,hello worl,k,hel,world,z,c, , w,z,b,f,hel,world,r,x,d,o worl,he,x, w,s,i,orld,o,d,t,hello,r,world,j,hello worl,o worl,he,w,f,e, worl,wor,o, worl,o w,lo, wor,lo wor,s,i,b,o worl,m,b,p,v, worl,b,lo ,worl,world,lo wor,f,orl,y,e,x,k,a,x,e,g,s,j,orl, w,d,orl,worl,s,a,worl,lo wor,lo ,o worl,s,lo worl,w,t,hel,orld,orl, worl,b,ll,g,o ,j,he,lo worl,n, ,he,c,n, worl, ,o worl,orl,p,k,b,he,o worl,z,orl,e,a,k,or,o w,z,w,lo w,z,f,u,k,s,o,he,o worl,m,h,a,k,o w,m,b,a,o,lo w,m,o w,he,a,hello,z,lo ,r,b,ll,l,he,or,hel,u, wor,he,g,t,o ,x,v,world,he,p,w,orl,lo,worl,o w, worl,lo w,b,orl,o worl, wor,r,he,h,hel,q,t,u,lo,w, w,lo wor,d,lo worl,n,hello,lo ,he,hello,lo wor,ll,lo worl,he,z,worl,orl, w, worl,lo worl,g,world,j,z,j,o, wor, wor,b,c,p,orl, wor,p,g,y, worl, ,b,k,q,g,o w,o worl,o ,p,d,orl,lo w,lo w,z,he,n,world,wor,d, worl,or,lo wor, wor,l,t,wor,worl,e,m, worl,z,j,hel,h,or,x,k, w,s,s,hello,b,p,lo w,l,g,p,o worl,j,wor,m, w,o,t,u,u,o,orld,s,u, w,orl,he,world,d,t,g,l,u,hello,n,worl,o w,lo worl,d,p,orl,q,o wor,u,v,or,q,d,c,hello worl,he,j,r,world,wor,o wor,hel,world,l,orld,q,x,wor,x,o ,ll,hello, wo,r,lo wor, ,or,j,o worl,t,hel,n,o,p, w,b,world,world,he,lo world,v,or,wor,o,lo world,lo worl,f,hello worl,u,orl,d, ,wor,z,r,lo w,p,o worl,o wor,b,he,f,hello wo,j,o ,o,or,f, ,o w,d, worl,wor,hel,k,y,hel,x,o worl, wor,g,ll, worl, wor,n, wo,orl,hel, wo,s,orld,he,lo,he, worl,o w,lo world,p,lo ,a,o ,v,c,p,t,or, w,q,f,o , wor,o worl,p,s,world,v,m,w,s,r,a,g,orl, ,z,p,v,j,o,o,r,l,c,q,orld,r,l,g,d,rl,lo wor,k,w,o , ,x,k,o,i,z,h,n,t,n, worl,w,w,s, wo,hel,he,f,lo , ,o worl,s,p,hello worl,r,o w,o worl,o w,j,c,world,lo worl,o ,wor,z,y,lo world,lo world,orld,s,u,hello,orl,lo wor,r,or,t,l,m,ll,worl,b,u, wo,o ,t, ,or,ll,ll,o,o w,llo,e,s,b,t,z,d,u,world,p,orld,wor,hello worl,lo worl,p,a,lo w,orld,w,wor,o w,lo worl,w,j,lo worl, worl,s,g,k,a,o w, ,o,hel,o,s,wor,u,w,p, wor,y,ll,he,j,orld,hello worl, worl,g,ll,o,lo worl,n,o,o worl,orld,m,lo,rl,o ,wor,hello worl,e,t,ll,g,d,d,orl,n,k,x,lo worl,a,q,wor,lo wor,lo worl,rl,o ,a,ll, wo,s,w,o w,e,h,lo,wor,o ,c,or,f,z,hel,lo worl,j,i,b,d,rl,lo ,j,j,o w,llo,i,b,z,c, worl,worl,e,o w,m, worl,wor,v,lo worl, ,r,u,y,g, w,m,r,ll,b, worl,g,o wor,b,a,m,n,orld,he,wor,hello,lo worl,orld, worl, , worl,o,q,b,o,e,rl,u,or, wo,u,o wor,hello worl,ll, ,llo,h, , ,wor,rl,y,l,z,he,orld,lo wor,x,g,n,b,world,j,ll,m,x,x,rl,n,lo worl,o worl,b, w, wo,b,z,x,o,v,or,t,hello,w,p,a,o,p,llo, ,y,d,p,h,c, wor,b,r,rl,u,c, worl,llo ,i,lo ,o ,q,p,w,he,he,b,lo,a,z,a,e, wor,v,or,hello wo,lo wor,m,hello worl,lo world,hello,v,worl,hel,s,llo ,e,d,o w,world,lo wor,lo ,hello worl,worl,w,w,orld,hello,o w,q,u,o ,worl,l,a,w, , wor,u,y,rl,s,p,o w,g,a,rl,v,y,orl,worl,o worl,rl,wor,x,u,or,s,orld,x,o ,q,p, w,z,u,t,d,a,orl,ll,o ,r,i,k,lo wor,p,b,a,ll,d,z,hello worl, ,hello worl, wor,o w,world,ll,world,hello,lo worl,k,llo ,hel,e,or,rl,hello,v,q, wo,lo wor,e,s,o,wor,lo ,o w,o ,or,x,wor,d,q,d,wor,hello wo,world, wo,a,llo ,worl,orld, wor,y,y,lo wor,o w, w,o,k,k,o ,b,llo worl,orld,worl,llo worl,ll,y,lo worl, wo,llo,hello,p, wo,u,hello worl,lo wor,m,n,orl,r,s,a, wor,wor,x,lo,u,lo world,lo world,s,o wor,o ,a,he,q,b,o,rl,o w,q,n, w, worl,e,a,k,o w, wor,a,f,o,hello worl, worl,o wor,z,g,s,o w, ,hello,hel,lo,i,lo worl,g,t,lo,lo world,rl,lo wor,o,t,ll,x,w,g,k,v,rl,he,y,hel,world,o wor,a,lo ,b,orl,lo, worl,q,o worl,world, w,hello wo,h,o ,o ,wor,hello,hel,lo ,b,q,o w,l,t,n,llo,e,q,q,q,lo worl,hello wo,orld,hello wo,h,x,p,z,hel,n,w,f,o wor,w,h,or,u,s,hello worl,hello ,d,d,rl,hello worl,wor,orl,hello,world,ll,lo,m,hello ,d,lo ,i,lo wor,orld,o ,z,m,hello wo,llo worl,ll,lo worl,world,hello ,llo,hello,e,rl,worl,h,llo worl,u,llo ,world,r,y,lo wor,g,z,d,worl,m,or,llo, wo,or,he,x,o worl,i,hello worl,k,f,w, w,o ,lo world,lo w,i,a,w,o ,z,r,hello ,hello ,hello worl,x,s,llo wo,u,worl,hello, worl,hello worl, ,world,t,llo world,rl, ,p,l,lo,lo w,worl,l, , ,rl,llo wo,h,o worl,llo worl,s,s,a,he,orld,p,lo ,i,f,hello wo,a,llo worl,llo,llo wo,he,llo ,b,ll, w,lo worl,i,t,k,world,r,llo ,lo worl,o w,d,j,lo worl,t,w,world,a,s,hello worl,or,hello wo,o ,llo wo, wo,u,orld,hello ,hello , worl,u,n,z,lo,o worl,llo , , wo,e,o wor,x,lo , w, world,s,hello ,lo world, world,worl, worl,b,h,h,q,world,s,c,lo w,d, ,l,hello worl,g,wor,or,t,x,i, worl,lo wor,s,p,s,llo worl,lo world,p,orld,f,k, w,orl, world,i,lo,orld,d,p,b, worl, ,world,b,b,ll,orl,l,a,llo ,p,k,world,i,hel,m,lo world,lo world,rl,world,d,q,r,he,j,hello worl,t,v,llo wo,p,d,g, world,world,r,hello,c,hello worl,llo world,lo world,z,m,t,q,j,t,m,d,n, worl,r,hello worl,lo worl,orl,p,hello ,g,o,rl,c,d,ll,lo w,o w,w,wor,orl, worl,llo world,y,llo world,o w, worl,c,g,lo worl, ,q,lo ,h,he,lo w,worl,lo worl,orld,m,u,wor, w,llo world,q,e,p,hello wo,hello worl,worl, world,s,o ,o ,d,o worl,n,x,world,hello worl,hello ,lo world, wo,x,rl,x,s,llo,lo ,a,hello ,e,q,lo w,world,x,i,o wor,w,z,s,o ,k,k,g,llo ,i,hello wo,lo w, worl, w,c, wor,c,c,lo , wo,lo world,lo,o wor,k,world,o wor,y,lo ,q,s,s, worl,hello ,lo , wor,orl,lo wor,llo,hello wo,wor, w,f, wo,w,k,r,j,o ,orld,i,or,p,b,rl,l,llo,e,rl,o,or,v,hello wo,lo ,w,j,w,hello,o w,hello worl,lo worl,e,i,llo,r,llo ,u,x,w,m,worl,h,wor,o, ,lo,o w,f,hel,c,lo world,b,a,llo worl,g,d,j,k,x,hello wo, world,o wor,llo world,hel,h,llo world,t,q,llo worl,x,h,lo ,v,or,b,u, wor,d,e,b,h,x,w,llo ,h,w, worl,o,hello, w, w,d,hello w,t,q,hello wo,llo wo,rl,m,lo wor,r,lo ,o w,hello,llo world,s,k,q,orld,y,v,hel,l,hello wo,w,a,orld,e, ,p, wor, wo,llo,wor,t,hello worl,f,hello w,wor,lo world,or,j,lo,d,i, worl, ,l,o ,wor,lo worl,g,b,m,s,s,ll,worl,orld,he,hello,rl,q,q,c,o worl,x,llo world,b,rl, ,d,ll,o, ,x,rl, wo,v,hel,llo world,l,hello,n,or,d,he,llo world"
word = "code golf and coding challenges", alphabet = "abcdefghijklmnopqrstuvwxyz " -> too large to fit in post
\$\endgroup\$
1
0
\$\begingroup\$

Morph a string into another

Given two strings consisting of only printable ascii, at least how many operations are needed to morph string a into string b?

The allowed operations are:

  • Take two characters x and y and make every instance of x in string a y.
  • Pick a letter l and delete all instances of it from either a or b, but not both. After deleting a letter l once, you may not delete that same letter l from either a or b again.

For instance, given a = "abc" and b = "ccc", the minimum number of operations is 2.

morph a -> b => bbc
morph b -> c => ccc

If no such sequence of morphs exists, output a value that is distinctable and would never be outputted with any possible input.

Test cases

"abc", "ccc" => 2
"abc", "abcz" => 1
"abbac", "ccbab" => -1
\$\endgroup\$
2
  • \$\begingroup\$ You should be more clear about what string a and b are in the example given. It can't be a -> b -> c if you are trying to get from a to b. also, is it really morphing a to b when you are changing both a and b? \$\endgroup\$
    – Tbw
    Feb 26 at 21:01
  • \$\begingroup\$ Also, you can do the last test case in 4 moves. "ccbab" -> "cca", "abbac" -> "bbc" -> "bba" -> "cca" \$\endgroup\$
    – Tbw
    Feb 26 at 21:03
0
\$\begingroup\$

There are way too few proof golf challenges for my taste, so I'd like to introduce a permanent one.

  • Is it too long or complicated?
  • My data is a work in progress, so there is still time before this challenge could potentially be ready.

The hardest logic puzzle game: Help me reduce my oversized proofs!

I put a lot of work into finding small proofs that elevate smallest-known single axioms to more practical (and popular) proof systems. Some are still large, can you find better proofs based on my data?

This challenge is all about finding some shorter proof(s) based on existing ones. The problems are similar to [CG question: (A → B) → (¬B → ¬A)], but based on different Hilbert systems, and vary in how to display and measure proofs. It also leaves much more choice on what to solve to the contestant. All parts are interconnected and might lead to improve each other. Choosing wisely which of the given pieces to tackle is part of the challenge!

For the sake of this logic challenge, the length of condensed detachment proofs in a certain prefix notation (so-called D-proofs) serves to measure the quality of solutions. The shorter the better!

Note that we use the same metric to measure proofs as in the reference of the best answer to the aforementioned question, in contrast to the amount of formulas that occur in a proof. So looking for multiple occurrences of a formula in the same proof and reducing by referencing only one of them is intentionally not a part of this.

Tournament Rules

All of the following rules are subject to be refined based on experience gained over time.

Rewards

This is an infinite challenge (up until I die and nobody maintains it anymore or I edit the question accordingly – planned: never). I will reward all my reputation points gathered here, down to 101, to best answers, provided they improve by at least 50 steps in total (for 50 points) w.r.t. to the previously given best answer (or my data if there is none), with points up to the number of improved steps (but capped at the maximum bounty of 500 points per solution). Once an improvement is confirmed, I will start the according bounty and award it as soon as possible.
Since I consider this question to be very challenging, I do not expect there to be many best answers in small time frames, but if that happens, I'll schedule the bounties according to timestamps of answers, and put in up to whichever spare reputation points are available when starting the bounty.
(If I do not react in reasonable time due to being absent here, you may comment in the discussions forum related to my project that this question arose from. This will drop me an email.)

There are no plans of using the accepted answer feature. This is in order to not give newcomers the false impression that this challenge has somehow already been ”solved”.
I consider each improvement quite the accomplishment, so I will of course upvote each improving answer, as soon as I found and verified it.

If this endless riddle fascinates you as well and you have spare reputation points (unlike me, at the time of writing this), feel free to contact me and/or edit this section on how you would like to contribute to these rewards.

Regardless, I would very much apprechiate if you could upvote this question so that I am able to reward deserving participants.

Challenge

There are seven theorems to prove in seven similar proof systems. The challenge is to minimize the proofs as much as possible. You may pick any number of theorems to prove in any of these systems, so there can be at most 49 evaluated proofs per solution.
Each combination varies in difficulty, and I will state a subjectively perceived difficulty (range 1 to 10) for each system. In the hardest system (called w2), three proofs are still missing (i.e. finding a proof is worth infinitely many steps regardless of its length). I initially provide D-proofs for all other combinations.

Some proofs are so long that surely there must be shorter ones, but several are already minimal or likely close to minimal, which can be seen by the number of steps covered by an exhaustive search, which I will also provide.

To avoid infinite scoring loopholes, I may treat all subproofs of intermediate theorems to be at most as long as previously shortest-known such proofs.
These proofs and my data are to be used as valuable hints. Starting from scratch would be way too hard, encourage terrible solutions, and break the unlimited scoring system.

Scoring

The score is the number of improved steps. As such it is always relative to the last best solution (which initially I provide). There are no negative scores: If you state a proof longer than a previously known proof, it will be worth 0 points.

For example, say there are two challengers A and B starting based on my data. Now challenger A improves proofs X and Y by 42 and 120 steps, respectively, and challenger B afterwards improves proofs Y and Z (≠ X) by 52 and 330 steps, respectively. Then first A receives a reward of up to 150 reputation points (which is the closest multiple of 50 that is at most 162 = 42 + 120). B improved by 340 = 10 + 330 = (52 - 42) + 330 steps relative to the previously shortest-known proofs, thus receives a reward of up to 300 points. Further assume that I only have 301 (thus 200 spare) reputation points when rewarding A, then A receives the full 150 points, leaving me at only 50 (above 101) left. Afterwards, B receives those 50 points together with those which I acquired in the meantime (multiples of 50, still capped at 300).

Note that there are not only timestamps but also increasing answer IDs to determine sequence of answers, so there can never be a tie in which answer came first. The answer ID acts as a tiebreaker for edits (which could potentially occur in the same second).

Answers

Answers should somehow provide an abstract representation similar to the one I provide, unless a D-proof is short enough to be stated in full (at most a few thousand characters), in which case it can be stated concretely. Of course, you can additionally provide the proof in whichever representation you like, e.g. with all used logical formulas, in infix notation, etc. An explanation on how you succeeded and where you failed would be nice, but is not required.

Only one (the first) answer per user is taken into account, but a proof-shortening edit is treated and scored like a new contribution at the time of editing. When there are multiple edits with multiple improvements, only the last edit is rewarded.

Improvements can be summarized in the title like “(<system>:<theorem>:<steps before>-><steps after>, ...)”, e.g. “(w2:A3:9001->1337, w4:id:465->379)”. However, the scoring will follow a procedure independent from such statements, and I might comment and/or request to edit relevant scoring information.

In case you would like to be mentioned by name (or pseudonym) for your contribution in my corresponding project and potential publications, please state so in your answer or via forum or email, and how. By default, I will use your username on Code Golf Stack Exchange.

You may even do some conventional code golfing to print your solution with as little code as possible. This may grant you upvotes, but no extra tournament points.
But in case your answer has already been rewarded and you find a further improvement, you can edit your answer and receive another reward – after dropping me a message so that I notice your edit. If there was no message and another answer received the corresponding reward due to your edit being unnoticed, your reward is lost (to another person).

Winning

Apart from the relative score, I'd like to treat this like a global game for which one can lead a “highscore” (but with lower numbers being better). Starting with three proofs unknown, the initial value is 3ω+c, where c is the sum of steps of smallest-known proofs, one for each solved target theorem. The game becomes even harder once it progresses, but latest successes automatically grant a top ranking. For that, I'll maintain a table below.

I have hopes that it will someday reach a finite amount close to several thousand steps. It seems plausible that this is possible when looking at high exponential growths in the amounts of theorems when doing exhaustive generations. Quantum computers might help a lot in the forseeable future.

One could say that somebody won this competition, when no other individual is able to find any shorter proofs anymore. But due to the complexity of the problem, this might as well take billions of years. I would guess that there are some alien races doing the same thing: After all, this concerns a few very special systems – all minimal 1-bases for {→,¬}‑propositional calculus.

Hall of Fame

Competitor Total Steps Date Recent Improvements
1. xamidi (profile) 3ω+20869754 Feb 03, 2024 initial proofs

Consecutive entries of the same user will be combined. Please let me know what you wish to be called or whether to link to a different site than only your Code Golf user profile.

Proof Systems

We are exploring the seven minimal 1-bases for classical propositional logic that use operators → (read: “implies”) and ¬ (read: “not”) with modus ponens (⊢ψ,⊢ψ→φ ⇒ ⊢φ, sometimes called “detachment”) as a rule of inference.

This rule can be read as “if (the proposition) ψ is provable and (the proposition) ψ→φ is provable, then thereby (the proposition) φ is provable”. An operator '⊢' for ”is provable” is not part of the propositional language. Propositions merely argue about truth, using '→', '¬', and other propositions. For example, the formula ψ→φ can be read as ”if (the proposition) ψ is true, then (the proposition) φ is true”. Suppose ψ→φ is true. When also ”(the proposition) ψ is true”, it follows via modus ponens that ”(the proposition) φ is true”. This kind of argument is the only one allowed in our proofs. Variables (such as ψ and φ) can be instantiated with arbitrary propositions (i.e. formulas in our propositional language).

Axioms

The axioms of our systems are Meredith's axiom and Walsh's six axioms. These can be stated in our propositional language as follows.

Different axioms are not allowed to be combined with each other. Indeed, each of these formulas is capable of deducing all theorems of propositional logic using only modus ponens as a rule of inference.

In order to save space, I will use standard Polish notation, a most concise (and well-googleable) prefix notation with (→,¬)=(C,N) for up to 26 different variables p,q,...,z,a,...,o, to state conclusions in proof summaries. You may use whichever well-defined formula representation suits you. Actually, a formula is simply a tree structure – follow the links in the leftmost column for graphical representations. A general way (which works for more than 26 different variables) to concisely state formulas is to use numbers as variables and separate them via ., e.g. CCCCC0.1CN2N3.2.4CC4.0C3.0 for Meredith's axiom.

Target Theorems

The target theorems are themselves axioms of popular proof systems, such as {A1,A2,A3} (“Łukasiewicz (L_3)-system”) and {L1,L2,L3} (“Łukasiewicz (L_1)-system”). Propositional axioms of Metamath's main proof database set.mm are also A1-A3.

Infix notation Polish notation
A1 ψ→(φ→ψ) CpCqp
A2 (ψ→(φ→χ))→((ψ→φ)→(ψ→χ)) CCpCqrCCpqCpr
A3 (¬ψ→¬φ)→(φ→ψ) CCNpNqCqp
id ψ→ψ Cpp
L1 (ψ→φ)→((φ→χ)→(ψ→χ)) CCpqCCqrCpr
L2 (¬ψ→ψ)→ψ CCNppp
L3 ψ→(¬ψ→φ) CpCNpq

Proving all axioms of a different proof system that is known to be complete (such as A1-A3 and L1-L3 both are under modus ponens) proves that the original system is complete by itself. There are also non-constructive ways to prove this, which is how we know that w2 is complete under modus ponens, despite such proofs still being unknown. The length of such proofs could help in finding proof theoretic bounds, which are still a big mystery in the field of proof complexity.

The authors of Walsh's paper called the task to find D-proofs from w2 to another system an “open challenge problem for automated reasoning”. Based on my data, it only remains to find a D-proof for L1. This is, however, by far the hardest optional part in this callenge, and I sure do not recommend it to anyone who does not wish to put an outstanding amount of effort into this.

Proof Notation

The operator for condensed detachment is the so-called D-rule, which takes two formulas as arguments, on which it applies tree unification to form the most general unifiers of ψ→φ and ψ, respectively, then applies modus ponens, which results in φ. Axioms in D-proofs are referred to by 1,2,…,9,a,b,…,z in their given order.

This way, given a sequence of axioms, a proof can be defined by a single prefix formula, e.g. DD211, which is evaluated like D(D(2,1),1), i.e. D is a 2-ary (partially defined) operator over the language of logical formulas.
The D-rule is only partially defined because unifiers to apply modus ponens on certain formulas may not exist.

Example

Let's determine DD211 for axioms (1,2):=(A1,A2). At first D21 entails that ψ→φ and ψ are instances of A2 and A1, respectively. Most general such unifiers are the instances (χ→(ξ→χ))→((χ→ξ)→(χ→χ)) and χ→(ξ→χ) of A2 and A1, which implies ψ := χ→(ξ→χ) and φ := (χ→ξ)→(χ→χ). Therefore, (χ→ξ)→(χ→χ) (i.e. CCpqCpp in Polish notation) is an intermediate theorem in DD211 = D(CCpqCpp)1. This entails that now ψ→φ and ψ are instances of (χ→ξ)→(χ→χ) and A1, respectively. Most general such unifiers are (χ→(τ→χ))→(χ→χ) and χ→(τ→χ), thus ψ := χ→(τ→χ) and φ := χ→χ. Therefore, DD211 proves the theorem χ→χ (i.e. Cpp in Polish notation). Combined, the D-proof DD211 w.r.t. (A1,A2) actually means:

Proposition Reason
1. ψ→(φ→ψ) (A1)
2. ψ→((φ→ψ)→ψ) (A1)
3. (ψ→((φ→ψ)→ψ))→((ψ→(φ→ψ))→(ψ→ψ)) (A2)
4. (ψ→(φ→ψ))→(ψ→ψ) (MP):2,3
5. ψ→ψ (MP):1,4

Alternatively, using Polish notation:

  1. CpCqp (1)
  2. CpCCqpp (1)
  3. CCpCCqppCCpCqpCpp (2)
  4. CCpCqpCpp (D):2,3
  5. Cpp (D):1,4

There are no such small examples in our single axiom systems, for example D11 in Meredith's system is already

  1. CCCCCqsCNCNpNtNrCNpNtpCCpqCrq (1)
  2. CCCCCCqsCNCNpNtNrCNpNtpCCpqCrqCCCCpqCrqCqsCtCqs (1)
  3. CCCCpqCrqCqsCtCqs (D):1,2

and formulas tend to blow up in size for longer proofs.
This illustrates that using formula-based proofs is extremely inefficient, whereas D-proofs are much lighter and can be processed by machines more efficiently.

Challenge Proofs

I will try to keep this information up to date.

The smallest-known D-proofs of target theorems have the following amounts of steps.

exhausted A1 A2 A3 id L1 L2 L3 overall difficulty
m 83 (+2) 13 7001 175 19 619 163 41 not easy - 5/10
w1 161 (+2) 33 1927 363 143 151 323 87 not easy - 5/10
w2 43 (+2) 53 - - 35 - 781 57 horrible - 10/10
w3 73 (+2) 67 18391835 1193987 135 1196969 6541 127 very hard - 8/10
w4 169 (+2) 59 16277 12959 465 14261 1889 53 bulky - 6/10
w5 55 (+2) 83 157 95 65 15 107 51 convenient - 3/10
w6 95 (+2) 19 18339 297 13 2743 125 37 not too bad - 4/10

For example, to the best of my knowledge I searched Meredith's system exhaustively for D-proofs of up to 83 steps. Since all its D-proofs have an odd length, all its smallest-known D-proofs with up to 85 steps are thereby minimal and cannot be reduced further. That is, if my search was actually exhaustive.

My (subjective) overall difficulty rating accounts for how hard I find searching and handling proofs, not for the apparent complexity of a system (which is indicated by “exhausted” – the higher the longer proofs are on average). The issue with a lower difficulty rating is that the given proofs might be so short already that it is very hard to find a smaller one (if it even exists). On the other hand, more difficult systems potentially give higher rewards.

Compact representations of these proofs are given below. Unfolding some of them results in exponential blowup, which explains the high number of steps asserted for concrete D-proofs. Index numbers of target theorems are highlighted as bold. More detailed and commented variants representing the same D-proofs are linked over the system names right to the bullet points (and as “[sample]” in my project's readme).

Puzzle Board (Abstract Representation)
    CCCCCpqCNrNsrtCCtpCsp = 1
[0] CCCppqCrq = D1D1D11
[1] CpCqp = DDD11[0]1
[2] CCCpqrCqr = D1D1D[0][0]
[3] Cpp = DDD[0][0]11
[4] CpCNpq = DD1[2][2]
[5] CCCpNCCCqrCNNqrNstCst = D1D1D[0]D1DD11DDDD1D1DD1DD11[0]111D1DD1D1D[1]D1D111
[6] CCpCpqCrCpq = DDD1D1D1D[0][5]11
[7] CCCpCqNCCrCNNssNqtCut = D1D1DD1DD1DDD1D1D[2]1D111D1D1D[0]D1DD11DDDD1D1DD1DD11[0]111D1DD1DD1D1D[0]1[1]D11DD1D11D11
[8] CCNppp = DD[6]DDD1D1DD1D1D[1]D1D11D[2]D[2]1111
[9] CCNpNqCqp = DDDDD1D1DD[2]1D[2]D[5]D1D1111DD1D1DD1D1D[2]1D11[1]1
[10] CCpqCCqrCpr = DD1DD1DDD[6][6]1[7]D1DDD[6][6]1[7]1
[11] CCpqCCrpCrq = DD[10]DD1DD1[7]1DD[6][6]1D[10][10]
[12] CCpCqrCCpqCpr = DD[11]D[10][10]DD[10][10]D[11]DD[6][6]1
    CCpCCNpqrCsCCNtCrtCpt = 1
[0] CCNpCCqrpCrp = DD1D1D111
[1] CCCCpCCNpqrstCst = D[0]D1D11
[2] CCCpqrCqr = D[0]D1D1D11
[3] CpCCNqCrqCrq = D1D[2]D[0]D11
[4] CpCCNqCCNrsqCrq = D1DDDD[2]111D1D1D11
[5] CpCqp = D[2][1]
[6] CpCNpq = DD[0][4]D[0][3]
[7] CCCCNNpCpNpqrCpr = D[0]D1D[1]D[1]DD[0]D11DD[0]D11[2]
[8] CCNpCqpCrCCNsCpsCqs = DD[0]DD[2]1DDD1DDD[1]1D1111D1DDD[1]1D111D[2]1
[9] Cpp = DD[4]1D[7][2]
[10] CCpqCCqrCpr = D[2]DD[0]D1[8][2]
[11] CCCCpqCrqsCCrps = D[0]DD[2]1DD[0]D1DDD[1]1D1D1D111[10]
[12] CCCCNpCqpprCqr = D[0]D1DD[0]D1D[1]D[1]1DD[0]D11D[0]DD[1]D[1]1D[7]D[0]DD[2]1[5]
[13] CCNppp = D[0]D[12]D[0][3]
[14] CCNpNqCqp = DD[2]DD1DD[0]D1D[2][8]D[0]DD[2]D[1]D[2]1D[7][2]1D[4]1
[15] CCpCqrCCpqCpr = DD[11]D[0]D1DD[0]D1D[1]D[2]1DD[0]DD[2]1DD[0]D1DDD[1]1D111[2]DD[0]D11D[0]DD[1]D[2]1D[7]D[0]DD[2]1[5]D[11]DDD[3]1DD[0]DDD1D111DD[0]D1DDDD[1]D[2]1D[1]D[2]DD[0]D11[6]1D1DDD[1]1D1D1D111D[2]D[2]DD[0][4]1D[12][2]DD[0]DDD1D111DD[0]DD[2]1D[0]D1DD[0]D1D[1]D[2]1DDDD[2]1D[0]DD[2]1DD[3]1DD[0][4]D[0]D1DDD[1]1D1111D11DD[0][4]1D[1]D[1]DD[0]D1DD[0]DD[1]1DD[0]D1DD[0]D1DDD[1]1D1111[2]1[2]
  • w2:   (missing: CCNpNqCqp,CCpCqrCCpqCpr,CCpqCCqrCpr)
    CpCCqCprCCNrCCNstqCsr = 1
[0] CpCCNqCCNrsCNqCCNCCNtCCNuvNpCutwNCxCCyCxzCCNzCCNabyCazCrq = DDDDD111111
[1] Cpp = DDD11DDD11D11[0][0]
[2] CpCqCrCsCtq = DDDDD1DDD11DD1D111[0]1[0]11
[3] CpCqp = DDD1D[2]1D111
[4] CpCNpq = DDDDD1D111[0]DDD11DDD1D111[0][0]1
[5] CpCqCrp = DDD11DD11DDD1D111[0][2]
[6] CCNppp = DDDDD1[1]1DDDD11DDD1[5]D11DDD11DDD1D111[0]1DDD1DDDD11D1DD1DDD1[0]D1111[0]DDD11D1[0][0]DDD1D1D[2]11[0]DDDDD11111[0]1DDDD11[5]DDD1DDD11D1DDD11DDD1D111[0]1DDD11DDD1DDD1DD1D111111[0]1DDD1DDD1DDD1DDD1[0]D1111[0]1[0]1[0]DDDDD11111[0]1DDD1DDDDD1D111[0]DDD11DDD1D111[0][0]DDD11DDD1111DDD11DDD1DDD1DDD11D11[0]111[0]1D1[1]DDDD11D11[0]DD1[3]1
    CpCCNqCCNrsCptCCtqCrq = 1
[0] CCCpCCqrCsrtCCCqrCsrt = DD1D111
[1] CCCpCqrsCCqrs = DD1DDDD111D[0]D11D111
[2] CCCpqrCqr = DDDDD[1]D111D[0]DD1111D11
[3] CCCNpqrCpr = DD11DDDDD111D[0]D11D1D11[1]
[4] CCNpCCNqrCCCCCCstuCtuvCCvwCxwyCCypCqp = D1DDD1[0]1D[0]DDDD[1]D11111
[5] CCNppCqp = DD11D[3]D11
[6] CpCqp = DDDDD[1]D111DD[1]D11111
[7] CpCCpqCrq = DDD1D11DDD[0]D[0]D1D[0]D1D11[0][1]D11
[8] CpCqCrp = D[2]D[1]DDDD111D[0]D11D11
[9] CCCNpqCCCCNrsCCtCutvCCvwCrwxCCxyCpy = D[1]D1D[1]D1[6]
[10] CCCCCpqrCsrtCqt = DD[1]DD[0]D[1]1[5]1
[11] CpCNpq = D[3]DD[0]D11[5]
[12] CCCpCqrsCrs = DD1[5]DDD[0]D[0]D1D[0]D11DD1[0]1[1]
[13] Cpp = DD[3]DD11[7]1
[14] CpCNNCqrCsCqr = DDD11DDD[1]DD[0]111DD[0]D[0]D1D11[0]DD[1]D[0]D1D[1]D1[6]DDD11DDD[1]DD[0]111DD[0]D[0]D1D11[0]DD1D11DDD11DDDDD111D[0]D11D1D11DD11DDD[0]D[0]D1[0]DD1DD1111[1]DDD11DDD[0]D[0]D1DDD1[0]1[0][1][1]DDDD111D[0]D11D1D11
[15] CCNCCppNqrCqr = D[9]DD1[13]D[14][14]
[16] CCNNpqCpq = D[9]D[4]D[2]DD[9]D[4]D[15][8][8]
[17] CpCqCrNNp = D[16][8]
[18] CCpqCNNpq = D[9]D[4][17]
[19] CCNpqCNCrpq = D[9]D[4]D[18]D[2][17]
[20] CCNpqCNCrCspq = D[9]D[4]D[18]D[12][17]
[21] CCCpqCNprCsCNpr = D[4]DD[9]D[4]D[18]D[3][17]D[10]D[7]D[3][15]
[22] CCNppp = D[16]DD[5]DD[9]D[4]D[3][17][5]D[5]DD[9]D[4]D[3][17][5]
[23] CCpNCNppCqNCNpp = D[4]D[18]D[10]D[7]DDD1[13]DD[4]D[19][8][7][22]
[24] CNCpqCrCsp = DDDDD1[13]DD[4]D[19][8][7][16]DD[4]DD[9]D[4]D[18]D[3][17][8]D[18]D[4]D[19][8]D[20]DD[21]DDD11DDD[0]D[0]D1[0]DD1[0]1[1]DDDD111D[0]D11D1D11DD[21][21]D[21][21]
[25] CCpCpqCpq = DDD[4][24]D[4][24]DD[4][24]D[4][24]
[26] CCpqCNCprq = D[9]D[4]DD[25][21]D[16]D[2]D[1]D[1]DDDD111D[0]D11D11
[27] CCCpqrCNpr = D[9]D[4]D[26][17]
[28] CCpqCCNppq = DD[1]D1D1D11D[4]DD[9]DD[9]D[4]D[18]DD[9][23][8]D[27][23][8]
[29] CpCCpqq = DDD[25]D[4]D[19][24]DDD[1]DD[0]111D[0]D[0]D1D[0]D11DDD1[6]DD[4]D[19][8][7][25]
[30] CCpqCCNqpq = D[4]DDD[1][4]D[28]D[10][25][28]
[31] CCNpNqCqp = D[16]DD[25]D[4]D[19][24]DD[30]D[2]D[3][15]D[19]D[25]DD[9]D[4]D[3][17][20]
[32] CCpqCCqrCpr = DDD1[26]D[6]D[28][29]DD[28][12]D[20]1
[33] CCpCqrCqCpr = DD[32][32]D[32][29]
[34] CCpCqrCCpqCpr = D[33]DD[32][32]DDD[28][12]D[20]1DD[33]D[27][30]D[33]DD[32][32][27]
    CpCCNqCCNrsCtqCCrtCrq = 1
[0] CpCCNqCCNrsCtqp = DDD1111
[1] CpCNCqrp = DDD111DDDD111D[0]11
[2] CCpCNqCCNrsCtqCpCCrtCrq = DD11D[1]1
[3] CCpqCpCCNrCCNstCurq = DD11D[1]D[0][0]
[4] CpCNpq = DDD11D[1][0]DDDD111D[0]11
[5] CpCqp = DDD111DDD11DDDD11D[1]DDD111D[0]1111
[6] CCpqCpCrq = DD11D[1]D[0][5]
[7] CCpNNqCpq = DD11DDD11D[1]D[3][0]DDDD111D[0]11
[8] CCpqCCrpCrq = D[2]D[6][0]
[9] CCpCqNqCpCqr = DD11D[1]D[0]DD11D[2]DDDD111DD111DDD11D[1]D[3][0]DDDD111D[0]11
[10] CCpqCpNNq = DD[2][3]D[9]DDD11D[1]D[0][7][5]
[11] Cpp = DDDDD[2]DD11D[1]D[0]D[3][5]D[6]DDD11D[1]D[0]DD11DDD11D[1]D[0]DD11D[1]D[0]DDD11D[1][0]DDDD111D1111DDD111D[1]1111
[12] CCNppp = D[7]DDD11DDD[2][3]D[1]D[6]D[9][5]DDD[2][3]D[9]DDDD11D[3]D[2]DDD11D[1]D[0]DD11D[1][4][1]DD1111DDDD11D[3]D[2]DDD11D[1]D[0]DD11D[1][4]DDD111D[1]1DD1111D[9][10]
[13] CpCCpqq = DDD[8][12]D[9]D[8]D[10][5]DDD[2][3]D[1]D[9][5]DDD[8][12]DD11D[1]D[0][4]DDD11D[1]D[0][6]DDD11D[3]DDD11D[1]D[0][4][5][11]
[14] CCNpNqCqp = DD[8]D[13][11]D[2]D[8][13]
[15] CCpqCCqrCpr = DDDD[8]D[13][11]D[2][3]DD[8][13]DDD11DDD11D[1]D[0]DDD11D[1]D[3][5]DDDD111D[0]11D[6]D[9][5][11]DDD11D[1]D[0][6][8]
[16] CCpCqrCCpqCpr = D[2]D[6]D[15][12]
    CCpqCCCrCstCqCNsNpCps = 1
[0] CCpqCCqrCpr = DD11D1DD11D1D11
[1] CCCpCqrCCCsqtCNqNsCsq = DDD11DD1D11D1DD1D11DD11D1DD11D1DD1D1DD11D11D1D111
[2] CpCNpq = D[1]1
[3] Cpp = D[1][0]
[4] CpCqp = DDD11DDD11DDD11D11D1DDD11DD11D1DD11D1DD1D1DD11D11DD11D1DD11D1DD1D1DD11D11D1D111D111
[5] CCNpNqCqp = DD1DD11DD1D1DD1D1D1D11D1D11D1DD1D11D1D11D1D1[2]
[6] CCNppp = DD1[0]DD11D1DD11D1DDD11D1D1DD11D1D1DD11D1DD11D1DD1D1DD11DD1D1DD1D1D1D11D1D11D1DD1D11D1D11D11D11
[7] CCpCqrCCpqCpr = DDD11D1D11DD1DD11D1DDD11D1[1]DD11D1DD1D1DD11D1DD11D1DD1D11D11D1D11D1DD11D1D1DD11D1DD11D1DD1D11D1[0]
[...989 bytes in 19 lines ommitted to fit into the sandbox...]

Where do I even start?

I called this a puzzle game for good reasons: Proofs for different theorems are components which can be used to build new components when arranged in a specific (and potentially very difficult to find) way. When it comes to snapping formulas together in order to create another one, things behave the same in all D-systems.

The above abstract proof representations hide many utilized formulas, but these can be viewed using pmGenerator to display the “full summary” mentioned in the linked proof files – deriving them by hand is probably too much of a workload. It may be useful, however, to write your own code to assist with this kind of work, and to follow your own ideas.

[...] (Does not fit into the sandbox.)

Data & Tools

pmGenerator

[...]

Prover9

[...]

TPTP / Vampire

[...]

\$\endgroup\$
2
  • 4
    \$\begingroup\$ So, uh, I didn't really read this, but it looks long and complicated. Is there a small simpler part that you could split off into a self-contained bite-size challenge? It's common here to post an easier version as Part 1 and follow it up with a Part 2 later. \$\endgroup\$
    – xnor
    Feb 14 at 23:58
  • \$\begingroup\$ There are a few problems with splitting up, like big gaps in difficulty for different systems and theorems, and potential loss of focus for what is essentially a never-ending interconnected challenge. I am currently thinking that Puzzling might be the better platform for this. \$\endgroup\$
    – xamid
    Feb 15 at 2:48
1
139 140
141
142 143
157

You must log in to answer this question.

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