572
\$\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\$
0

4674 Answers 4674

1
5 6
7
8 9
156
5
\$\begingroup\$

Implement the random Fibonacci sequence

\$\endgroup\$
15
  • \$\begingroup\$ Is -3 a valid output for f5? \$\endgroup\$
    – tsh
    Aug 31, 2020 at 6:27
  • \$\begingroup\$ But it is possible that f3 = 2. It is also possible that f4 = -1. \$\endgroup\$
    – tsh
    Sep 1, 2020 at 1:52
  • \$\begingroup\$ @tsh It is possible that f3 = 2 and it is possible that f4 = -1, but the two cannot be satisfied at once. So the challenge requires to record the previous results, I think (and therefore some short approaches like naive recursion can't be used). \$\endgroup\$
    – Bubbler
    Sep 1, 2020 at 2:45
  • 1
    \$\begingroup\$ It would be good to include the correct distributions of the first few entries, like f_3 to f_6, for testing purposes. \$\endgroup\$
    – Zgarb
    Sep 1, 2020 at 7:46
  • \$\begingroup\$ @cairdcoinheringaahing f3 = f2 + f1 = 1 + 1 = 2; f4 = f3 - f2 = (f2 - f1) - f2 = (1 - 1) - 1 = -1; f5 = f4 - f3 = -1 - 2 = -3; If this is not what you want, you may need to update your description to avoid ambiguous. \$\endgroup\$
    – tsh
    Sep 2, 2020 at 1:45
  • \$\begingroup\$ @tsh Took me a while, but I think I understand what you're getting at. Does my latest edit address that? \$\endgroup\$ Sep 8, 2020 at 22:18
  • \$\begingroup\$ @Zgarb Not the best when it comes to distributions, but I've added in a list of possible values for n = 1 ... 6 \$\endgroup\$ Sep 8, 2020 at 22:18
  • \$\begingroup\$ I was going to edit in the distributions, but I don't believe your last case is correct. I don't think there is a way to reach 6 or -3. I decided to edit it in anyway since I wrote it on a scrap of paper, but of course feel free to change it if I am wrong. \$\endgroup\$ Sep 9, 2020 at 21:14
  • \$\begingroup\$ If given n we just output f_n, this voids the requirement that the sequence should remember previous values, doesn't it? \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 16:14
  • \$\begingroup\$ @LuisMendo No, the requirement that the sequence "remembers" previous values is means that tsh's comment above would be an invalid way to construct the sequence. Because \$f_n\$ is constructed from previous terms, those terms cannot change partway through the construction of the sequence. For example, while constructing \$f_6\$, you'd have to first get the values for \$f_{1,\dots5}\$. Then, when constructing \$f_7\$, the values of \$f_{1,\dots5}\$ would be the same as when getting \$f_6\$, whether they were outputted or not. \$\endgroup\$ Sep 12, 2020 at 16:18
  • \$\begingroup\$ Ah, I see, So, "remember" means that in the construction of a given f7, every occurrence of f1 etc should have the same value. \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 16:44
  • \$\begingroup\$ @LuisMendo Yes exactly. If you have a better wording, I'd love to hear it, I'm not too happy with "remember" \$\endgroup\$ Sep 12, 2020 at 17:18
  • \$\begingroup\$ @cairdcoinheringaahing Here's a suggestion: Each random realization of the sequence must use consistent values. For example, if [...] \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 20:22
  • \$\begingroup\$ Also, when you say is chosen at random, you probably mean is chosen at random independently of previous choices? This prevents the code from randomly choosing a sign and using it for all terms, for example \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 20:23
  • 1
    \$\begingroup\$ @LuisMendo That wording is nice, thanks! And yes, each choice should be independent, I'll edit that it \$\endgroup\$ Sep 12, 2020 at 20:59
5
\$\begingroup\$

Minimise a bijection \$\mathbb{N}^n\to\mathbb{N}\$

\$\endgroup\$
9
  • \$\begingroup\$ Seems very possible. You can iterate the cantor pairing function \$\pi(\pi(\pi(a,b),c)\ldots)\$ \$\endgroup\$
    – Sisyphus
    Oct 17, 2020 at 2:08
  • \$\begingroup\$ @Sisyphus, yes, but can you iterate it \$n\$ times within \$n\$ bytes? \$\endgroup\$ Oct 17, 2020 at 11:58
  • \$\begingroup\$ Also, I like this scoring idea but I fear that the abstractness of the task will scare away potential golfers. Maybe it would be better to choose a simpler task that has n as a parameter. \$\endgroup\$
    – Zgarb
    Oct 18, 2020 at 19:42
  • \$\begingroup\$ @Zgarb While I do agree that, because it's much harder with the self-referential part, a simpler challenge would probably do better (votes/answers wise), but I've got no issue with this going unanswered, and I think as is, it'll draw much more impressive answers with a more discriminating choice of bijections. \$\endgroup\$ Oct 18, 2020 at 19:44
  • \$\begingroup\$ Finally, you're missing the condition that every natural number must occur as an output. \$\endgroup\$
    – Zgarb
    Oct 18, 2020 at 19:45
  • \$\begingroup\$ Plus, because of the self-referential part, I think that this doesn't close the door on any future challenges that allow you to choose your own \$n\$, or take \$n\$ as a parameter, so I'm happy with this scoring criteria. Also, thanks for noticing that, edited in. \$\endgroup\$ Oct 18, 2020 at 19:46
  • \$\begingroup\$ I don't really see the point of the n-is-length idea. It seems like you just have to write code that works for any n, then plug in n equal to the length of the code (accounting for the replacement). Only perhaps an ultra-golfy language might be able to do something like n=2 in 2 bytes rather than writing a general solution. \$\endgroup\$
    – xnor
    Oct 18, 2020 at 21:41
  • \$\begingroup\$ @xnor IMO, it adds an extra level of complexity/difficulty to the challenge, in that you have to modify the actual code as you modify code length. Also, I don't think the generic "take \$n\$ as a parameter" version is particularly interesting, whereas requiring answers to link \$n\$ and their code is \$\endgroup\$ Oct 18, 2020 at 22:03
  • \$\begingroup\$ @cairdcoinheringaahing Can you give an example of an interesting thing a program could do in linking its code length? I'm really not seeing it. The only extremely minor thing I could see is that if you have, say, a 76 byte program that works excepts it has a spot you need to put the number in, you need to put in 78 to account for the length of the code and number. \$\endgroup\$
    – xnor
    Oct 18, 2020 at 22:10
5
\$\begingroup\$

Quickly! Group together!

\$\endgroup\$
4
  • \$\begingroup\$ This seems like fun! I have one concern, though. The first is that keeping track of all of the restrictions that have already been used seems like an unnecessary headache. Testing if a language has been used is fairly easy using the SE search (you might want to add in some premade links to make it easier for people to do) and I think that will help the variety enough. This seems like it would become a headache faster than it is worth, even if you did something like updating the challenge each day. \$\endgroup\$ Nov 13, 2020 at 2:59
  • \$\begingroup\$ @FryAmTheEggman Yeah, that's my main concern is keeping track of everything. Maybe adding a Stack Snippet to the challenge body that extracts previously used restrictions could alleviate that (similar to what we did with my OEIS answer chaining for used sequences)? I'm hesitant to remove the rule about not reusing restrictions, because it could just lead to the challenge continuing ad infinitum with a couple of basic, repeated restrictions \$\endgroup\$ Nov 13, 2020 at 13:50
  • \$\begingroup\$ Trivial restrictions are so numerous that I don't believe this rule is doing anything relevant to end the challenge faster. I'd recommend dropping it and thinking about some other way to limit solutions if you really want that. \$\endgroup\$ Nov 13, 2020 at 16:46
  • \$\begingroup\$ I agree with @FryAmTheEggman about the restrictions. Your rule that languages can't be used on different days should be enough to ensure that the challenge ends eventually. \$\endgroup\$ Nov 22, 2020 at 23:47
5
\$\begingroup\$

Is it a vampire number?

\$\endgroup\$
4
  • \$\begingroup\$ The old challenge certainly suffers from strict I/O, but I don't have a strong opinion as to whether it should be closed in favour of this one. If you do go ahead, I suggest clarifying that \$x\$ and \$y\$ must both have the same number of digits and only one of them may end with 0. \$\endgroup\$
    – Dingus
    Jan 20, 2021 at 22:10
  • \$\begingroup\$ @Dingus "strict I/O" is a bit of an understatement. I have a Jelly answer to this and the old one. This is 10 bytes, the only one is 45 bytes, and the difference in length comes entirely from having to format the output to meet the rules, which no-one likes doing. Good spot on the restrictions on \$x\$ and \$y\$ \$\endgroup\$ Jan 21, 2021 at 9:19
  • \$\begingroup\$ I definitely see your point. I'm not opposed to the repost, in case I wasn't clear. \$\endgroup\$
    – Dingus
    Jan 21, 2021 at 21:42
  • \$\begingroup\$ I vote for the repost \$\endgroup\$
    – anotherOne
    Jan 22, 2021 at 20:09
5
\$\begingroup\$

I decide to change the statement a little, so people who don't know the language can easily understand the challenge. (apparently there are many)


Background:

  • I'm thinking about scraping some BF programs on this site for the fastest-code (or approximation) version of the other challenge, and I figure out that I need to have this, and I post it here as a code-golf challenge since it's somewhat interesting (and also pretty easy).
  • It's possible to force programs to check if there are any extra characters too; however it might make the problem harder (only allow printable ASCII? Some scraped data might have non-ASCII characters, so it isn't really practical. Any Unicode characters as input? Most esoteric languages can't handle that.)

Does this BF program have a simple memory layout?

Given a string consisting of only the characters +-[]<>., check if:

  • All pairs of [] are matching (balanced), and
  • There's an equal number of < and > between every matching pair of [].

Background: the inputs that this program output true are exactly the valid inputs for the related challenge BF memory layout optimizer.

Reference implementation in Python 3.

Example input/output

Output true:

,>>,
,<++[->>+<<]
+<><>+
,[.,]
>.<

Output false:

,[>,]
+[>>>->-[>->----<<<]>>]>.---.>+..+++.>>.<.>>---.<<<.+++.------.<-.>>+.
].[

Undefined behavior: (your program can do anything when given those as input)

((((()()()()()){}){}){}())
$\="=".hex.$/
\!$/'?))='%<\..>
\$\endgroup\$
3
  • \$\begingroup\$ can you please make the rules a list, some of us are bad at reading. \$\endgroup\$
    – Alex bries
    Feb 4, 2021 at 9:30
  • \$\begingroup\$ @Alexbries But there are only two of them... \$\endgroup\$
    – DELETE_ME
    Feb 4, 2021 at 9:46
  • 1
    \$\begingroup\$ I was worried for a bit this would delve into Rice's Theorem territory (the similar question "does this BF program have bounded memory consumption?" would). Seems plenty simple though. \$\endgroup\$
    – Beefster
    Feb 10, 2021 at 23:18
5
\$\begingroup\$

KoTH: Hunter-Gatherer Society

, ,

In this challenge, the goal is to write a bot (Javascript function) which survives for as long as possible with its tribe. The bots are placed on an island, with the ability to hunt, gather, farm, and build. Tribes can fight, and the last alive wins.

This challenge is complicated, and it's designed to be that way. I'd recommend starting out with bots that specialize in a particular type of strategy, like gathering berries or fighting. To keep this post from being longer than it already is, technical details will be included in the links labeled More at the end of each section. (Meta: These links don't go anywhere yet)

Overview

Bots have hit points and hunger. In order to survive, bots need to eat. There are various foods, such as berries from berry bushes, bread from farming, and meat from hunting. Materials like sticks, rocks, logs, and ores can be found around the island, and used to make tools and buildings.

The island has grasslands, forests, and rivers. Rabbits and elk can be hunted for meat and hide, with sticks, rocks, or spears. Meat can be cooked over a campfire. Tribes can build walls to protect their farms and bases, and fight to defend them with weapons and armor. Bots can talk to their tribe members, and trade for rare materials.

Hit Points, Hunger, and Turns

All bots have a number of hit points, and a number of hunger points. Bots start with 7.5 hit points, out of a maximum of 10. When they reach 0 or below, they die. Various actions take hunger. Bots start with 75, out of a maximum of 100, and when they drop below 0 hunger points they instead lose 10% of the hunger taken in hit points.

Games consist of a number of turns. During each turn, all bots can perform actions including moving, eating, harvesting, and fighting. Each action takes a certain amount of hunger, and every action performed in the same turn after the first one doubles the hunger taken.

More: Turns

Terrain

The world consists of a square grid, with a radius determined by floor(25 * sqrt(bot_count)) + 25. The center of the grid will always be [0, 0], with coordinated ranging from [-radius, -radius] to [radius, radius]. Positions will always be specified in absolute coordinates as an array [x, y], and most actions that take a position argument will require the bot to be adjacent to that position unless otherwise specified.

This land is divided into four biomes:

  • Grassland
  • Forest
  • River
  • Ocean

The outer ring of 25 grid squares will be ocean. This consists of a beach closer to the center, with water continuing to the boundary of the world. Rivers will generate similarly, usually with a width of 5-10, with a thin beach on each side.

Each naturally generated terrain square can be one of the following:

  • Plain
  • Bush
  • Berry bush
  • Tree
  • Stone
  • Copper ore
  • Iron ore
  • Sand
  • Water

Grasslands are mostly plain, with some stones and bushes. Forests are more interesting, with many trees and some stones, bushes, and berry bushes.

More: Terrain

Movement

Bots can move in any of four directions: north(), east(), south(), or west(). Only some terrain can be walked into:

  • Plain
  • Sand
  • Farmland
  • Bush (+1)
  • Berry bush (+1)
  • Water (+2)

It typically takes 1 hunger to move. However, moving into certain terrain (marked with +1 or +2) can take extra hunger. An addition hunger point is taken for every 10 items the bot is holding, rounded down. Multiple bots can occupy the same position.

Food

There are four foods, which restore different amounts of hunger:

  • Berries: 10
  • Meat: 15
  • Bread: 25
  • Cooked meat: 40

Foods also restore 10% of their hunger restoration in hit points.

Berries can be collected from berry bushes, by returning harvest() when adjacent to (or standing in) a berry bush. Meat is obtained by hunting, bread is crafted with grain, and cooked meat requires a campfire.

Grain can be initially collected by returning harvest() when adjacent to (or standing in) plain land. It can also be collected from farming. Bread can be crafted by returning craft(Item.BREAD) while holding 1 grain and 1 rock. The rock will not be consumed.

More: Food, Harvesting

Resources

Many types of terrain can be broken by returning break(position), turning into plain land and giving items:

  • Bush: Stick × 1
  • Berry bush: Berries × 1
  • Tree: Log × 2
  • Stone: Stone × 1
  • Copper ore: Copper ore × 1
  • Iron ore: Iron ore × 1

Trees require an axe to break. All four will reappear after a number of turns if the land remains plain.

A stone axe can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_AXE), and will break after 10 uses.

More: Breaking, Crafting

Farming

A stone shovel can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_SHOVEL). A shovel can be used to turn plain land into farmland, and will break after 20 uses. This is done by returning shovel(position).

Grain can be planted on farmland by returning plant(position). It will take around 100 to 200 turns to grow, although the amount of time is much shorter within 20 squares of water. Grain starts as Growth.NOT_GROWN, and cannot be harvested (only broken). It then becomes Growth.GROWING after about 70% of the total time, and will give one grain when broken or harvested. Finally, the last stage is Growth.GROWN, where two to four wheat are given from harvesting.

More: Farming

Hunting

A stone spear can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_SPEAR). A spear can be used to hunt, as well as a stick or stone. Bots can attack at a position by returning attack(position) (hunt(position) and fight(position) are aliases). Movement happens before attacking, so simply attacking an animal's current position may not work. If attacking would hit multiple targets, damage is distributed between them evenly.

Sticks and stones have a range of 1, with sticks dealing 0.35 hit points, and stones dealing 0.75. Spears deal one hit point, with a maximum range of 2. A spear breaks after 10 successful hits. Attacking takes 10 hunger, whether or not any target is successfully hit.

There are two types of animals: rabbits and elk. Rabbits have 1 hit point, and elk have 4. Rabbits will move every 1 to 2 turns, avoiding bots if they are very close. Elk will move every 2 to 4 turns, and will always move away from attackers for 2 to 4 turns after being attacked. Rabbits will give the last bot to hit them 1 meat, and have a 25% chance of giving 1 hide to the second to last player to hit them. Elk are similar, giving 1 meat and 1 hide to the last bot to hit them, and 1 meat to the bot that hit them the 2nd to last time.

More: Hunting

Tribes

All bots will be part of a tribe. Tribes are determined by the creator of the bot, can contain any number of bots from any number of writers. Bots in the same tribe will be able to recognize each other, while bots outside their tribe will only have their tribe name known. Tribe members cannot attack each other.

If a tribe member is next to another one, they can give an item with give(name, item), or transfer any JSON-serializable data with talk(name, data).

Armor can be crafted from 2 hide with craft(Item.ARMOR). When a bot is holding armor, it can take up to 10 hit points before breaking. Bots fight with other bots in the same way they hunt animals. When a bot is killed, its items are distributed among the bots that attacked it recently according to the damage done.

More: Tribes, Fighting

Building

Bots can build walls and campfires, by returning build(build, position), where build is one of Terrain.WOOD_WALL, Terrain.STONE_WALL, Terrain.CRATE, or Terrain.CAMPFIRE. Wood walls require 2 logs, and take 10 hits with an axe to break, giving the bot that breaks it one log. Stone walls require 4 stones, and take 75 hits with an axe to break, giving the bot that breaks it one stone.

Crates require 1 log and 1 bronze, and can store items. If you're adjacent to a crate, you can store items in it with store(position, items), and take an item with take(position, items). Crates can store up to 40 items. The contents of crates are visible to any bot.

Campfires require 1 stone, and 2 sticks, and can be used to cook meat. Campfires can be given fuel using fuel(position, item), accepting sticks, logs, and charcoal. Bots can cook meat or logs (which turn into cooked meat and charcoal, respectively) using cook(Item.MEAT) or cook(Item.LOG), if adjacent to a campfire. Cooking meat uses 3 fuel, and cooking logs uses 5. A stick provides 1 fuel, a log provides 5, and charcoal provides 15.

A campfire can be broken with an axe, and will give the bot that breaks it all of the unused fuel it holds. Partially consumed logs or charcoal will not be given.

More: Building, Cooking

Upgrading

Copper ore and iron ore can be cooked into bronze and iron in a campfire, requiring 10 and 15 fuel respectively. Bronze and iron can be used to craft stronger axes, shovels, and spears, by replacing the stone in the recipe with the corresponding item.

For axes and shovels, the material affects the durability:

  • Stone axe: 10
  • Bronze axe: 15
  • Iron axe: 25

All shovels have twice the durability of a similarly strong axe. Spears are different, with all tiers having 10 durability. Instead, the number of hit points dealt is upgraded:

  • Stone spear: 1.0
  • Bronze spear: 1.5
  • Iron spear: 2.5

Because these items are so rare, trading might be a good way for a tribe to advance. By returning offer(sell, buy), any bot can offer a number of items they have (sell) for a number of items they want to have (buy). All bots will receive an array of offers made on the last turn, and can accept one with accept(offer), where offer is an offer ID.

The sell array should contain IDs of items the bot is holding, while buy should be an array of objects. All objects should have an item property with the Item wanted, and an optional durability property can specify a minimum durability acceptable. If no minimum durability is included, only undamaged items will be accepted.

More: Trading

Bots

Many arguments and functions involve enums including Terrain and Item. Here is a reference:

  • Terrain: PLAIN, BUSH, TREE, STONE, COPPER_ORE, IRON_ORE, FARMLAND, SAND, WATER, WOOD_WALL, STONE_WALL, CAMPFIRE
  • Item: STICK, BERRIES, LOG, STONE, COPPER_ORE, IRON_ORE, CHARCOAL, BRONZE, IRON, MEAT, COOKED_MEAT, GRAIN, BREAD, HIDE, ARMOR, STONE_AXE, BRONZE_AXE, IRON_AXE, STONE_SHOVEL, BRONZE_SHOVEL, IRON_SHOVEL, STONE_SPEAR, BRONZE_SPEAR, IRON_SPEAR
  • Growth: EMPTY, NOT_GROWN, GROWING, GROWN
  • Animal: RABBIT, ELK

All bots should be Javascript functions, which take four arguments:

  • grid: A 15 by 15 grid centered around the bot, with all items being objects:
    • terrain: A type of Terrain
    • details: An object, with a has_berries property for Terrain.BUSH, a growth property for farmland (Growth.EMPTY if no grain is planted), a hit_points property for walls (starts as 10 for wood or 75 for stone), and a fuels property for campfires (array of Items.STICK, Items.LOG, and Items.CHARCOAL, does not include partially burned)
    • bots: An array of bots, with all being objects:
      • tribe: A string containing a tribe name
      • name: A string containing a bot name, if the bot is in the same tribe
    • animals: An array of animals, with all being one of Animal.RABBIT or Animal.ELK
  • bot: An object with information about the bot:
    • hit_points: Hit points
    • hunger: Hunger
    • position: Position as [x, y]
    • items: An array of items held, with all items being objects:
      • id: A unique ID for this item
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the remaining uses (or hit points) until broken
  • offers: An array of offers from other bots on the last turn:
    • id: An ID unique to the offer
    • sell: An array of the items the seller is offering:
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the remaining uses (or hit points) until broken
    • buy: An array of items the seller wants:
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the minimum durability acceptable
  • talking: An array of data sent from other bots on the last turn:
    • name: The name of the sending bot
    • data: The data sent by the bot
  • storage: An object that can be used for storage between turns

Meta

(Note that none of the links to More work yet)

  • Is this clear enough as it is, without the technical details?
  • Is there too much information, or is it too hard to read?
  • Do you think there will be strategy and clever bot design?
  • Would you compete in this challenge? Why not?

New features

Things I recently added:

  • Trading between tribes
  • Communication within tribes
  • Bronze and iron, and better tools
  • Crates to store items
\$\endgroup\$
8
  • \$\begingroup\$ When you say "Bots start with 75, out of a maximum of 100, and when they drop below 0 hunger points they instead lose 10% of the hunger taken in hit points." Did you mean: "Bots start with 75 hitpoints, out of a maximum of 100, and when they drop below 0 hit points they instead lose 10% of the hunger taken in hit points."? \$\endgroup\$ Mar 9, 2021 at 4:58
  • \$\begingroup\$ @DanielOnMSE The reverse, mostly. Bots start with 7.5/10 hit points, and 75/100 hunger. When a bot drops below 0 hunger, additional hunger is taken from the bot's hit points instead (but scaled by 10%) \$\endgroup\$ Mar 9, 2021 at 5:19
  • \$\begingroup\$ Ahh okay. I think this contradicts "Bots start with 7.5 hunger, out of a maximum of 10. When they reach 0 or below, they die" Unless hitpoints/hungers still mean something when dead? Nice idea btw. I've upvoted. I'll continue to trawl through it and see if I can find any errors. I think I get what you are trying to say with the hitpoints/hunger but I think you may have accidentally swapped the two in some places? \$\endgroup\$ Mar 9, 2021 at 5:28
  • \$\begingroup\$ @DanielOnMSE Ah, I see what you mean. I'll fix that. \$\endgroup\$ Mar 9, 2021 at 5:44
  • \$\begingroup\$ Just food for thought. Might make the challenge more approachable if you wrote a script that created the world state and takes input/gives output every turn to the bots? Or is part of this challenge making the "game" itself? Perhaps you've already considered this and made something. Whether or not this is implemented will determine the complexity of this, imo. Like if you could create something everyone involved could use to test their bot? Also give it fixed input and output formats? \$\endgroup\$ Mar 9, 2021 at 5:53
  • 2
    \$\begingroup\$ @DanielOnMSE Usually that's part of making a KoTH, yeah. There's a controller program (usually written by the author before posting) that manages all of the bots, sets up the games, determines the winner, etc. \$\endgroup\$ Mar 9, 2021 at 13:21
  • \$\begingroup\$ This challenge seems very interesting but even more complex to me... but I'd give it a try. However, it would need many participating bots to utilize all of its features and make it fun to play. Technical note: break won't work as a function name (it's reserved) unless it's an object property. \$\endgroup\$
    – FZs
    May 18, 2021 at 15:38
  • 1
    \$\begingroup\$ @FZs Part of my goal when designing this KotH was specifically for it to be very complex; I'm hoping bots will be sort of forced to specialize. Thanks for noticing the break thing, I guess I'll rename that to destroy or mine \$\endgroup\$ May 18, 2021 at 15:40
5
\$\begingroup\$

Liars and Guessers

\$\endgroup\$
8
  • \$\begingroup\$ this looks like a very good challenge. I'd go with JS for the language. \$\endgroup\$ Feb 28, 2021 at 14:16
  • 1
    \$\begingroup\$ Be careful. If the minimax algorithm is not too hard, then people can just implement it and effectively block all the other answers. \$\endgroup\$
    – DELETE_ME
    Feb 28, 2021 at 14:55
  • \$\begingroup\$ Isn't JavaScript very good for sandboxing? The browser is the sandbox. / Besides, you can ask people to explain suspicious code, obviously... \$\endgroup\$
    – DELETE_ME
    Feb 28, 2021 at 14:56
  • \$\begingroup\$ @user202729 Re sandboxing I was less worried about safety than clever people inspecting the program's memory/whatever. But I guess I can just forbid it. \$\endgroup\$
    – Miriam
    Feb 28, 2021 at 14:58
  • \$\begingroup\$ @user202729 Re minimax, I was worried that it might be too trivial to come up with a perfect solution. I'll look into it. \$\endgroup\$
    – Miriam
    Feb 28, 2021 at 15:00
  • \$\begingroup\$ IMO, either Python or JS would be suitable to this question. You can chose any of them and it should work fine. As this question is asking about strategy of guessing instead of golfing in specified languages. People try to answer this question are not required to know very details of the language used. \$\endgroup\$
    – tsh
    Mar 9, 2021 at 6:00
  • \$\begingroup\$ To my understanding, guesser_score = sum(times_guessed for number in ([0..255] repeat 10 times) for each liar), lower is better. (10 times repeating is required since most submission would relay on some random behaviors.) liar_score is defined similar but higher is better. Use liar_score - guesser_score or liar_score / guesser_score (I would prefer the div one) to get score for some answer. \$\endgroup\$
    – tsh
    Mar 9, 2021 at 6:16
  • \$\begingroup\$ Wrote a Python implementation. It treats liars and guessers as separate submissions. \$\endgroup\$
    – Miriam
    Mar 9, 2021 at 15:35
5
\$\begingroup\$

Self-Replicating Numbers

\$\endgroup\$
13
  • 1
    \$\begingroup\$ Nice challenge, but I feel it would be more interesting if it took two inputs, m and n, and outputted either the first m n-order numbers or the mth n-order number. \$\endgroup\$
    – user
    Mar 5, 2021 at 15:29
  • \$\begingroup\$ @user I do like that; my original concept for the challenge was similar (outputting the first n distinct orders). I think your concept is more interesting, but I do worry about the run time - I'll run some tests and see if there are enough reasonable test cases. Thanks for the feedback! \$\endgroup\$ Mar 5, 2021 at 15:34
  • \$\begingroup\$ For the formatting thing, see math.meta.stackexchange.com/questions/5020/… -- replace $ with \$. \$\endgroup\$
    – DELETE_ME
    Mar 6, 2021 at 10:54
  • \$\begingroup\$ Add "exactly" (appear [...] exactly \$n\$ times [...]) in the definition too, if that's what you mean. \$\endgroup\$
    – DELETE_ME
    Mar 6, 2021 at 10:55
  • \$\begingroup\$ +1 nice challenge! I have no idea of how to verify that there are no 1st-order self-replicating numbers after 9. \$\endgroup\$
    – anotherOne
    Mar 7, 2021 at 12:55
  • 1
    \$\begingroup\$ @SheikYerbouti Thanks! Think of it this way; since you're checking all multiples of a number up to their square, every number from 10 and up will have the multiple of itself and ten checked - any number times ten is guaranteed to have the original number as a substring. Numbers from 100 and up will have the multiple of itself and 100 checked, and so on. \$\endgroup\$ Mar 7, 2021 at 14:42
  • \$\begingroup\$ Oh you are right! That's clever (or I am slow ahaha) \$\endgroup\$
    – anotherOne
    Mar 7, 2021 at 15:29
  • \$\begingroup\$ Allowing output of the infinite sequence of n-order numbers would be nice. \$\endgroup\$
    – Razetime
    Mar 9, 2021 at 14:44
  • \$\begingroup\$ @Razetime I wanted to make it a little more challenging by requiring both inputs - would it make sense to allow outputting the infinite sequence of numbers that are either m or n order, or is that too complicated? I want there to be reasons to choose either output option, if I choose to add more, and I fear that the infinite series of n-order will be the easier choice for a majority of languages. Let me know if I'm just overthinking it, and thanks for the feedback! \$\endgroup\$ Mar 9, 2021 at 16:02
  • \$\begingroup\$ @ZaelinGoodman many recent sequence challenges allow output in 3 main ways: nth number, first n numbers or an infinite sequence. It is up to you to choose what you think suits the challenge best. \$\endgroup\$
    – Razetime
    Mar 9, 2021 at 16:08
  • \$\begingroup\$ @Razetime Ohhh okay; I looked at a few other sequence challenges and pulled together a few options - I do think it rounded out the challenge a bit more, but now I'm not sure how better to format the test cases area to accommodate those additional output modes \$\endgroup\$ Mar 9, 2021 at 16:45
  • \$\begingroup\$ Minor things: can you change the wording and formatting of the "The CHallenge" section to make it more obvious that you need to do one of the things (see some existing sequence questions for more info)? Also can you clarify that you mean a substring in decimal? Can you clarify that "if the input is not valid" means "if no such number exists". Finally, what tags are you planning to use? code-golf sequence number ...? \$\endgroup\$
    – pxeger
    Mar 10, 2021 at 17:19
  • 1
    \$\begingroup\$ @pxeger Thanks, I have implemented all of your suggestions - let me know if you still feel any of those areas are lacking! \$\endgroup\$ Mar 10, 2021 at 18:41
5
\$\begingroup\$

Minimally destroy CGCC in Game of Life

\$\endgroup\$
8
  • \$\begingroup\$ Just to clarify, you get an integer \$n\$ as input and must kill all but \$n\$ cells from the initial state to produce the shortest lived automata? \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 17:44
  • \$\begingroup\$ Are there performance requirements? This problem is in EXPTIME. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 17:45
  • \$\begingroup\$ @Beefster No time requirements. And no, you decide how many cells you want to make alive (call that \$n\$) and which cells they are. You then run the game with those cells and the initial CGCC being alive until it reaches a point where all cells on the board are dead. Lowest \$n\$ wins. \$\endgroup\$ Mar 22, 2021 at 17:47
  • \$\begingroup\$ Oh, I get it. You're supposed to add live cells around the initial CGCC so that the board eventually anihillates. The way you framed the challenge is a little confusing. You make it seem like you're supposed to remove cells from the initial configuration. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 18:02
  • \$\begingroup\$ @Beefster I've edited the wording slightly, does it make more sense? \$\endgroup\$ Mar 22, 2021 at 18:05
  • \$\begingroup\$ The wording is clearer now, but the issue is that "However, if we change the initial state to the following, by changing 13 cells, then, after 31 iterations, the board is empty" is sort of misleading because it prepares the reader to remove cells when you then say "And this is your task." I think it would be less confusing if you gave an example where adding cells to an initial state causes the pattern to eventually annihilate. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 19:20
  • \$\begingroup\$ @Beefster The issue with that is that I don't actually have an example that fits the current rules :/ \$\endgroup\$ Mar 22, 2021 at 19:38
  • \$\begingroup\$ You don't necessarily need to create an example that fits the rules. You could instead give an example of a simpler pattern that, when a few additional cells are made live, leads to eventual annihilation. So the overall flow of the challenge description would be something like this: simple pattern, simple pattern + live cells --> annihilation, CGCC pattern creates still life + oscillators, description of the task and scoring. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 20:02
5
\$\begingroup\$

Posted

\$\endgroup\$
1
  • \$\begingroup\$ Instead of saying that "Output is undefined if n<1, or if A is shorter than n" just specify that this won't be the case. \$\endgroup\$
    – Adám
    Mar 24, 2021 at 13:54
5
\$\begingroup\$

Two Diehards Make a Glider


POSTED

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Is the WIP for the title or the challenge? The challenge looks mostly ok, but I'd be worried about having many solutions with the form: as simple as possible for the gliders with a well-known diehard placed far away. For the title, something like "gliders as emergent properties" or something could also be catchy. \$\endgroup\$ Mar 24, 2021 at 22:01
5
\$\begingroup\$

I'm Jelly of Python (Cops)

I'm Jelly of Python (Robbers)

\$\endgroup\$
5
\$\begingroup\$

Decode Polybus Square/Tap Code/Prison Code

\$\endgroup\$
4
  • \$\begingroup\$ Nice challenge :) You need to add a scoring criterion (code-golf most likely), and you should provide a few input->output examples to help checking answers \$\endgroup\$
    – Leo
    Mar 22, 2021 at 23:03
  • \$\begingroup\$ Suggested testcases: 23 15 31 31 34 => HELLO, 24 25 31 32 => IJLM, 11 22 33 44 55 => AGNTZ. Add tags code-golf, decode and string. \$\endgroup\$
    – emanresu A
    Mar 23, 2021 at 8:11
  • \$\begingroup\$ Thanks for the feedback :) \$\endgroup\$ Mar 23, 2021 at 12:51
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted \$\endgroup\$ Mar 30, 2021 at 15:15
5
\$\begingroup\$

Plz Halp I Need $$$ Again

Bob’s startup is running out of money and desperately needs investors to keep it afloat. Although you have helped Bob find the maximum number of investors, Bob has quickly realized that more investors does not lead to more funds because different investors give different amounts of money. Each investor interested in Bob’s company wishes to schedule a meeting with a certain start and end time, and promises to invest a certain amount of money. However, some of the meetings times may conflict. What is the maximum amount of money he can get from his investors?

Input Format

Input is given as an array of tuples of integers (or the equivalent in your chosen language). Each tuple p represents one investor, where p[0] is the start time of the investor’s meeting, p[1] is the end time, and p[2] is the amount of money promised.

For example, in the test case [(0, 10, 30), (10, 20, 50)], there are two investors: one who wants to meet from time 0 to time 10 and offers $30, and one who wants to meet from time 10 to time 20 and offers $50.

Meetings will always have a positive duration, meeting times are always non-negative, and a meeting that ends at time k does not conflict with a meeting that starts at time k. You may assume that the input is nonempty, and you may use any reasonable I/O method for input.

Within reason, you may also take input in different formats (for example, as three lists, one which contains the start times, one with the end times, and one with the money offered).

Output

Your program should output an integer, the maximum quantity of money that Bob can make.

Test Cases

[(1, 100, 10), (1, 5, 3), (5, 10, 3), (10, 15, 3)] => 10
[(0, 30, 40), (20, 45, 30)] => 40
[(10, 40, 40), (60, 85, 60)] => 100
[(65, 100, 70), (10, 45, 80)] => 150
[(10, 15, 50), (50, 85, 10), (95, 110, 60)] => 120
[(100, 135, 80), (50, 70, 80), (80, 110, 30), (95, 100, 40)] => 200
[(65, 95, 70), (50, 75, 30), (35, 60, 80), (85, 115, 100)] => 180
[(30, 35, 80), (35, 65, 10), (75, 110, 40), (40, 45, 20)] => 140
[(80, 110, 50), (0, 5, 30), (95, 125, 50), (80, 85, 70)] => 150
[(25, 40, 10), (100, 115, 60), (15, 50, 90), (60, 95, 50)] => 200
[(100, 125, 50), (75, 80, 100), (30, 60, 20), (50, 65, 90)] => 240
[(15, 35, 80), (55, 70, 40), (30, 65, 90), (30, 55, 60)] => 120
[(15, 40, 50), (60, 95, 30), (35, 40, 70), (55, 60, 90)] => 190
[(40, 65, 80), (40, 75, 10), (5, 15, 80), (100, 115, 80), (15, 35, 100), (60, 95, 40)] => 340
[(5, 30, 60), (85, 105, 90), (35, 65, 80), (90, 115, 40), (85, 90, 80), (30, 60, 90)] => 270
[(55, 65, 30), (5, 15, 90), (50, 85, 100), (0, 15, 90), (65, 70, 70), (60, 70, 80), (35, 55, 20), (80, 105, 80)] => 290
[(0, 10, 90), (70, 85, 80), (45, 55, 20), (90, 105, 90), (55, 90, 50), (0, 25, 20), (85, 105, 30), (85, 90, 100)] => 380
[(10, 45, 40), (85, 115, 80), (85, 105, 30), (30, 50, 50), (20, 40, 80), (100, 115, 60), (100, 135, 70), (30, 35, 70), (35, 50, 30)] => 180
[(80, 105, 70), (60, 65, 50), (95, 105, 80), (55, 65, 100), (40, 75, 80), (95, 110, 70), (60, 70, 90), (65, 70, 50), (55, 85, 100)] => 230
[(80, 85, 70), (35, 40, 60), (60, 80, 80), (5, 20, 100), (30, 60, 100), (45, 50, 60), (45, 80, 60), (10, 20, 50), (50, 65, 60), (60, 85, 70)] => 370
[(50, 75, 100), (90, 115, 20), (50, 65, 10), (35, 50, 30), (90, 120, 90), (65, 90, 30), (20, 55, 40), (50, 75, 50), (75, 105, 10), (15, 35, 70)] => 290

Rules

  • Standard loopholes are prohibited.
  • Though not required, polynomial-time solutions are encouraged so that Bob does not have to wait forever for the result.
  • This is , so the shortest solution in each language wins.

Meta

  • Are there any errors with the computer-generated test cases? I've manually verified some of them but I may have overlooked something.
  • Is there any ambiguity in the problem statement?
  • Are there any other issues?
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Test cases seems be ordered by end times. I'd suggest mixing them up (so no answer accidentally uses the order) or specifying the order. Also, in the example in the input format, it's (10, 20, 50) but you say they want to meet 5 - 10. (And I prefer the Output section before the test cases, so people know what they need to do earlier.) \$\endgroup\$
    – xash
    Apr 28, 2021 at 12:51
  • \$\begingroup\$ Thanks, I have edited the challenge accordingly \$\endgroup\$
    – knosmos
    Apr 28, 2021 at 12:55
  • 1
    \$\begingroup\$ Is it possible to take input as three lists, for start times, end times, and prices? \$\endgroup\$
    – rak1507
    Apr 28, 2021 at 13:13
  • \$\begingroup\$ Sure - should I add test cases in that format? \$\endgroup\$
    – knosmos
    Apr 28, 2021 at 13:16
  • 2
    \$\begingroup\$ You don't need to add testcases in different formats, simply state in your post that different formats are acceptable (and perhaps mention some different formats like the \$3\$ lists @rak1507 mentions). \$\endgroup\$
    – Noodle9
    Apr 28, 2021 at 13:41
  • \$\begingroup\$ Link to the deleted main post, so that it's easy to find and edit when this challenge is good to go :) \$\endgroup\$ Apr 28, 2021 at 15:21
5
\$\begingroup\$

posted

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I think I saw l4m2's proposal which is essentially the same thing, but this one is arguably much better and clearly worded. Btw, the first example is just a special case of Chaitin's constant with power-of-0.5 weights. \$\endgroup\$
    – Bubbler
    May 12, 2021 at 14:16
  • \$\begingroup\$ I don't see how it's possible, if \$f(n)\$ is computable, isn't the limit of \$f(n)\$ computable by the definition of limit? \$\endgroup\$ May 12, 2021 at 17:31
  • \$\begingroup\$ @CommandMaster Actually no! This is just one of a million ways in which limits can be counter intuitive. For an example, imagine an \$f\$ where \$f(n)\$ just takes the first \$n\$ Turing machines and runs them for \$n\$ steps, if machine \$m\$ halts in the test run then you add \$2^{-m}\$ to a total (think about what this means in binary). This is obviously computable, we can simulate Turing machines for \$n\$ steps and add rational numbers. But the limit encodes the exact solution to the halting problem. This is actually the first example number there. \$\endgroup\$
    – Wheat Wizard Mod
    May 12, 2021 at 17:48
  • 1
    \$\begingroup\$ Does \$f(n)\$ have to be an exact rational (i.e. a pair (numerator, denominator)), or can it be represented as a floating point number? In other words, can we output \$f(n)\$ as a floating point number which will, necessarily, be inexact for large values of \$n\$, as long as the algorithm theoretically works if given arbitrary precision? \$\endgroup\$
    – Delfad0r
    May 12, 2021 at 20:30
  • \$\begingroup\$ @Delfad0r I'm not entitled to answer your question, but I don't think float or double are applicable here. Arbitrary-precision floating-point numbers are certainly applicable tho. \$\endgroup\$ May 12, 2021 at 20:44
  • \$\begingroup\$ @WheatWizard Thanks for the clarification! Does the first option include, say, a pair [numerator,denominator] (even though it's not a built-in rational type)? In this case, is the pair required to be reduced (i.e. gcd=1)? \$\endgroup\$
    – Delfad0r
    May 13, 2021 at 10:09
  • 1
    \$\begingroup\$ @Delfad0r I will add that as another form, and the second format shows a non-reduced fraction as an example so it would be all right for this format as well. \$\endgroup\$
    – Wheat Wizard Mod
    May 13, 2021 at 10:11
5
\$\begingroup\$

Drop some boxes

\$\endgroup\$
1
  • \$\begingroup\$ Assuming you live in a world with gravity \$\endgroup\$
    – math scat
    Jun 20, 2021 at 10:07
5
\$\begingroup\$

Ouput Input... Forever

Problem

Given input chars, output them repeatedly forever.

Examples

abc       -> abcabcabcabcabcabcabcabcabc...
[1, 2, 3] -> [1, 2, 3][1, 2, 3][1, 2, 3]...
lo        -> lololololololololololololol...

Dedication: This is for all the tarpits out there!

Questions

  • Should a delimiter be allowed?
  • I was imagining that the input would be cycled through infinitely in order, like in the examples. Should we enforce that as a rule, though?
    • Or should the rules just be: Each char of input should eventually occur infinitely many times in output. (Informally stated, but can easily be made mathematically precise.)
  • Other thoughts!
\$\endgroup\$
4
  • \$\begingroup\$ If you go with "Each char of input should eventually occur infinitely many times in output", then you'd need to specify that no other characters should be outputted because otherwise you could just output all bytes in order, or output random bytes infinitely \$\endgroup\$
    – pxeger
    Aug 6, 2021 at 7:24
  • 1
    \$\begingroup\$ I think that vast majority of languages here will just use some version of x = input(); while(true) {print(x);}, so I doubt this will be especially interesting except for in a handful of languages \$\endgroup\$ Aug 6, 2021 at 13:49
  • \$\begingroup\$ Are you going to post this? :) \$\endgroup\$
    – emanresu A
    Aug 13, 2021 at 22:30
  • \$\begingroup\$ Are you going to post this? It's been a month.... \$\endgroup\$
    – emanresu A
    Sep 6, 2021 at 3:31
5
\$\begingroup\$

Create the shortest code snippet of the power functions 1 through 10 which can be compiled to assembly code and which contains the minimum number of imul assembly operations. For better comparison use https://godbolt.org/ and either GCC or LLVM.

Introduction

Did you know the fastest way to calculate x⁴ is not x*x*x*x, but y = x*x; y*y which saves one multiplication and is therefore faster. In mathematics and computer science this is called addition-chain exponentiation.

The minimum number of multiplications for powers of 1 through 10 are

x^1  -> 0
x^2  -> 1
x^3  -> 2
x^4  -> 2
x^5  -> 3
x^6  -> 3
x^7  -> 4
x^8  -> 3
x^9  -> 4
x^10 -> 4

Example

The assembly code looks as follows (C++ code below):

pow_1(int):
        mov     eax, edi
        ret
pow_2(int):
        mov     eax, edi
        imul    eax, edi
        ret
pow_3(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, edi
        ret
pow_4(int):
        imul    edi, edi
        mov     eax, edi
        imul    eax, edi
        ret
pow_5(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, edi
        ret
pow_6(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, edi
        imul    eax, eax
        ret
pow_7(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, edi
        ret
pow_8(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, eax
        ret
pow_9(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, eax
        imul    eax, edi
        ret
pow_10(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, edi
        imul    eax, eax
        ret

One naive solution written in C/C++ and compiled with X86-64 gcc 11.2 and -O3 optimization on https://godbolt.org/ could be (Notice that I didn't need to optimize the code myself, but the compiler picked it up automatically. Aren't compilers awesome?):


int pow_1(int num) {
    return num;
}

int pow_2(int num) {
    return num * num;
}

int pow_3(int num) {
    return num * num * num;
}

int pow_4(int num) {
    return num * num * num * num;
}

int pow_5(int num) {
    return num * num * num * num * num;
}

int pow_6(int num) {
    return num * num * num * num * num * num;
}

int pow_7(int num) {
    return num * num * num * num * num * num * num;
}

int pow_8(int num) {
    return num * num * num * num * num * num * num * num;
}

int pow_9(int num) {
    return num * num * num * num * num * num * num * num * num;
}

int pow_10(int num) {
    return num * num * num * num * num * num * num * num * num * num;
}

Of course you can also use other language like Rust to create the same assembly code:

pub fn pow_9(num: i32) -> i32 {
    num * num * num * num * num * num * num * num * num
}

(Note Rust has an additional mov, but the challenge only focuses on the amount of imul assembly instructions.)

example::pow_9:
        mov     eax, edi
        mov     ecx, edi
        imul    ecx, edi
        imul    ecx, ecx
        imul    eax, ecx
        imul    eax, ecx
        ret

Scoring

  • The string must be compilable to assembly instruction with a compiler like GCC or LLVM (Note they have backends for many languages). You are not allowed to create the assembly instructions directly. Please also provide compiler version and flags.
  • The whole string must be written in the same language (no writing C with another language)
  • Out of bounds issues must not be considered, the code should work for integers 0 through 3.
  • The generated assembly code can only contain the minimum number of imul needed for that power and mov and ret instructions
  • The 10 functions in the assembly instructions should be named as I named them (order does not matter)
  • Shortest string wins!

Good luck!

Discussion

I've mistakenly posted this as a question to the meta site, but wanted this was my intended destination. After a few migrations the current location is here. I've now reposted here trying to keep the style the same as I couldn't edit the post anymore.

Grain ghost has made two comments on how to improve the challenge:

  • "Creating the assembly instructions not via a compiler is not allowed" and "The generated assembly must be similar to the provided assembly" strike me as not particularly clear, objective or enforceable
  • Since we are dealing with assembly I would expect some discussion about precision and out of bounds issues

Thank you!

This is not a typical code golf challenge, but I'm very excited what kinds of meta programming techniques will show up.

\$\endgroup\$
10
  • \$\begingroup\$ @grain-ghost do I ping you this way? What I want to prohibit with the use of a compiler is that people simple create a program creating the assembly instruction string. The string must be compilable with GCC or LLVM. Similarity is hard, because compilers are weird (see my Rust example). May be say: The binary must contain the right number of imul instructions, at most two additional mov instruction and one ret instruction. Precision is no important with integer numbers as far I can think. Overflow is an issue, but I would simply neglect that case or restrict to numbers below or equal to 3. \$\endgroup\$
    – JulianWgs
    Nov 16, 2021 at 20:54
  • 1
    \$\begingroup\$ If nobody's said it so far, welcome to Code Golf! This looks like a great challenge. For out of bounds issues, there's usually one of two approaches challenges will take, either having a minimum input size that must be supported, or just ignoring out of bounds issues within reason. Those would probably both work here, so it's entirely up to you. I agree with the two bullet points Grain Ghost brought up, those could probably use some clarification. \$\endgroup\$ Nov 16, 2021 at 21:06
  • \$\begingroup\$ Thanks for welcoming me! :) I've updated the challenge. By restricting the amount of assembly instructions the submission must use imul (another feedback brought up to use for loops with addition) and guarantees similarity, because there is no other way to solve it. Another idea I had would be to only allow mov, ret and imul instructions. \$\endgroup\$
    – JulianWgs
    Nov 16, 2021 at 21:24
  • 1
    \$\begingroup\$ Oh, so you're aiming to restrict what instructions can be used? That makes sense, I hadn't understood the wording right. You can definitely just choose a specific list of instructions to allow, which I'd recommend doing instead of the current requirements which are a little bit vague. There's actually a tag for that sort of thing, atomic-code-golf. \$\endgroup\$ Nov 16, 2021 at 21:27
  • 1
    \$\begingroup\$ (Comment migrated from the original question.) In addition to what was already pointed out on the main site, another potential issue with this challenge is that it's entirely possible to do it without any imul, for instance with inefficient addition loops. \$\endgroup\$
    – Arnauld
    Nov 16, 2021 at 21:32
  • \$\begingroup\$ I've updated the challenge accordingly I think limiting to imul (minimum number), mov and ret ensures similarity. I would like to encourage entries from many languages. Can I pick a winner per language? \$\endgroup\$
    – JulianWgs
    Nov 16, 2021 at 22:04
  • \$\begingroup\$ We have a challenge on a similar topic Shortest Addtion Chain. This challenge looks different enough though. \$\endgroup\$
    – xnor
    Nov 17, 2021 at 2:00
  • 2
    \$\begingroup\$ I might not be the target audience as someone not into compiled languages, but the needing to go through a compiler strikes me as convoluted. What if we could just output the assembly, or some other representation of the sequence of operations? Needing to consider how a compiler would translate and optimize the operations seems finicky, but I guess maybe that's the whole point. \$\endgroup\$
    – xnor
    Nov 17, 2021 at 2:06
  • \$\begingroup\$ @xnor exactly the best solution will probably involve some kind of metaprogramming massaging the code so the compiler will optimize it. I've updated the challenge again with info about naming the functions. Can the challenge be posted now? :) \$\endgroup\$
    – JulianWgs
    Nov 17, 2021 at 7:00
  • 1
    \$\begingroup\$ @JulianWgs It's your decision, but the general recommendation is to leave posts in the Sandbox at least 72 hours to gather feedback. I'd err on the side of waiting for this challenge because it might benefit from being seen by more people with knowledge in this specific domain and many people don't look at the Sandbox that often. I'd also suggest confirming with existing commenters that your edits have addressed their comments. \$\endgroup\$
    – xnor
    Nov 17, 2021 at 7:06
5
\$\begingroup\$

Open or close?

Posted here.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ The calculator would be more useful if ) were followed by ) assuming another unbalanced ( remains. Example: "1*(2+(3*4)" -> ? \$\endgroup\$
    – aschepler
    Nov 15, 2021 at 23:24
  • \$\begingroup\$ @aschepler Good thing the calculator dev thought this through more than I did, because that's exactly what it does. I'll update the question, thanks! \$\endgroup\$
    – Jitse
    Nov 16, 2021 at 8:11
5
\$\begingroup\$

Convert prefix to infix

\$\endgroup\$
2
  • \$\begingroup\$ Dupe? \$\endgroup\$
    – Dingus
    Nov 18, 2021 at 23:09
  • \$\begingroup\$ @Dingus Yes, I'll just do prefix to infix instead :P \$\endgroup\$
    – emanresu A
    Nov 19, 2021 at 3:31
5
\$\begingroup\$

Minimum number of changed tiles to permit knight passage

Summary

Given a chess knight K that is only allowed to step on permitted tiles X, output the minimum number of . tiles that must be changed to an X tile in order to permit a passage to the destination D.

Specification

  • The chessboard is guaranteed to be larger than 3x3.
  • The chessboard is guaranteed to have one and only one D and K in it.
  • Sometimes, not using the existing X tiles can lead to a more minimal solution, so please take this in mind while solving this challenge. (e.g. the 2nd testcase)

Test cases

..D.
XXXX
....
...K

Output = 1 (sequence = (-2,+1), (+1,+2))

.D..
....
..XK
....

Output = 2: (sequence = (-2,+1), (-1,-2), (+2, +1), (-1, +2))

D.X
...
...
...
..K

Output = 1: (sequence: (-1, +2), (-1, +2))

DX.
...
...
...
..K

Output = 1: (sequence: (-1, +2), (-1, +2))

D.X.
....
.X.X
.K..

Output = 0: (sequence: (+2, +1), (-1, +2), (-1, -2), (-1, +2))

DXXX
XKXX
XXXX
XXXX

Output = 0: (sequence: (+1, -2), (+1, +2), (-2, +1), (-1, -2), (+2, +1), (-2, +1))

\$\endgroup\$
14
  • \$\begingroup\$ where is the D on the board and what is the W doing on the board \$\endgroup\$
    – DialFrost
    Jan 26, 2022 at 7:08
  • 1
    \$\begingroup\$ @DialFrost That's a typo. Fixed \$\endgroup\$
    – user110579
    Jan 26, 2022 at 7:10
  • \$\begingroup\$ i like this challenge otherwise! \$\endgroup\$
    – DialFrost
    Jan 26, 2022 at 7:15
  • \$\begingroup\$ @DialFrost Thank you! :) \$\endgroup\$
    – user110579
    Jan 26, 2022 at 7:22
  • \$\begingroup\$ May we assume that using existing X tiles leads to minimal solution or may there be "traps"? \$\endgroup\$
    – pajonk
    Jan 26, 2022 at 8:08
  • \$\begingroup\$ May you give an example of not using the X tiles leading to the minimal solution? \$\endgroup\$
    – user110579
    Jan 26, 2022 at 8:12
  • \$\begingroup\$ I mean e.g. DX./.../.../.../..K, where putting X in the middle is sufficient and you don't need to reach the existing X. \$\endgroup\$
    – pajonk
    Jan 26, 2022 at 8:12
  • 1
    \$\begingroup\$ @pajonk In this case, I think I'm trying to define a challenge that allows "traps" in the input. I'll clarify that in the challenge. \$\endgroup\$
    – user110579
    Jan 26, 2022 at 8:14
  • \$\begingroup\$ I've edited my example in the meantime to highlight its "trappy" nature. You may also want to add more test-cases (like with more Xs or where the ouput is 0). \$\endgroup\$
    – pajonk
    Jan 26, 2022 at 8:18
  • \$\begingroup\$ @pajonk I've added your edited testcase and some of your testcase suggestions. Thank you for your suggestions! \$\endgroup\$
    – user110579
    Jan 26, 2022 at 8:27
  • \$\begingroup\$ your first test case is wrong, you can do it in 1: (-2,+1), (+1,+2) \$\endgroup\$ Jan 26, 2022 at 14:06
  • \$\begingroup\$ @thejonymyster Fixed \$\endgroup\$
    – user110579
    Jan 27, 2022 at 4:57
  • \$\begingroup\$ suggested testcase: one where the straight path to the goal takes more X tile placements than following a longer route to the goal which already has many X tiles. Either way though, this is pretty much ready to post \$\endgroup\$ Jan 28, 2022 at 14:13
  • \$\begingroup\$ May I assume the board is less than (or equals to) 8x8? \$\endgroup\$
    – tsh
    Jan 29, 2022 at 8:15
5
\$\begingroup\$

Is it a fibonacci-like sequence?

\$\endgroup\$
2
5
\$\begingroup\$

Fibonacci triangle

\$\endgroup\$
8
  • \$\begingroup\$ this is more of a curve due to the incrementing length of numbers :P looks alright tho \$\endgroup\$
    – DialFrost
    Mar 2, 2022 at 3:47
  • \$\begingroup\$ @DialFrost Close enough, and I wasn't sure what else to call it :P \$\endgroup\$
    – emanresu A
    Mar 2, 2022 at 3:48
  • \$\begingroup\$ i think the test case for 20 is wrong, the first 1+1=2 and 1+2=3 dont align \$\endgroup\$
    – DialFrost
    Mar 2, 2022 at 3:48
  • \$\begingroup\$ @DialFrost Fixed, that's an error with my programming \$\endgroup\$
    – emanresu A
    Mar 2, 2022 at 3:51
  • \$\begingroup\$ suggestion for title qns: Fibonacci curve (cuz triangle has no application to this qns lol) \$\endgroup\$
    – DialFrost
    Mar 2, 2022 at 4:17
  • \$\begingroup\$ Is infinite output allowed, taking no input? (part of standard sequence rules) \$\endgroup\$
    – pxeger
    Mar 2, 2022 at 10:17
  • \$\begingroup\$ @pxeger Sure :P - no outputting the nth term though, as I feel that makes the challenge too easy. \$\endgroup\$
    – emanresu A
    Mar 2, 2022 at 19:03
  • 1
    \$\begingroup\$ @emanresuA Yes, I was thinking that as well. (although calculating the increasing string lengths might be complicated?) \$\endgroup\$
    – pxeger
    Mar 2, 2022 at 20:09
5
\$\begingroup\$

Gray code on N symbols

\$\endgroup\$
5
\$\begingroup\$

Resolve references in a chat discussion

\$\endgroup\$
5
\$\begingroup\$

Pairs of integers ordered by their exponentiation

\$\endgroup\$
5
\$\begingroup\$

Convert between graph representations.

\$\endgroup\$
2
  • \$\begingroup\$ Awesome challenge! It seems ready to me and juding by the upvotes (might wanna wait 1 or 2 more days) \$\endgroup\$
    – DialFrost
    Mar 21, 2022 at 11:00
  • \$\begingroup\$ @DialFrost already posted .... \$\endgroup\$
    – zoomlogo
    Mar 21, 2022 at 12:21
5
\$\begingroup\$

Satisfy as many people as possible

Posted here.

\$\endgroup\$
2
  • \$\begingroup\$ im confused but nice challenge! :D \$\endgroup\$
    – DialFrost
    Mar 14, 2022 at 2:50
  • \$\begingroup\$ Wow, good challenge! They should use this for making servant robots; they'd make everyone as happy as possible :-)! The only part I didn't understand was the math formula; but, since I don't even know what the giant E means, that's not surprising. And as for title suggestions, something a little more catchy would be nice. Maybe something along the lines of "How many people can you satisfy?" (that's just a suggestion; I'm not very good at creative writing) \$\endgroup\$ Mar 22, 2022 at 19:37
5
\$\begingroup\$

Unshuffle my poker chips

\$\endgroup\$
5
\$\begingroup\$

Storing a band matrix

\$\endgroup\$
2
  • \$\begingroup\$ Can you clarify in the definition that a band is symmetric (in terms of shape) about the main diagonal? Something like "the main diagonal and an equal number of adjacent diagonals on either side of it" \$\endgroup\$
    – att
    May 9, 2022 at 23:02
  • \$\begingroup\$ Wait never mind, somehow I missed the "in this challenge" further down \$\endgroup\$
    – att
    May 9, 2022 at 23:04
1
5 6
7
8 9
156

You must log in to answer this question.

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