515
\$\begingroup\$

What is the Sandbox?

This "Sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on 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.

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

\$\endgroup\$
0

3273 Answers 3273

1
14 15
16
17 18
110
3
\$\begingroup\$

Byte-sized Huffman Coding (WIP)

Huffman codings are a method to compress data with certain frequency properties, usually text. Normally, these operate on bits rather than bytes, but this challenge will instead operate on whole bytes instead. Since you wouldn't get any benefit otherwise, you can represent multiple consecutive characters with a sequence of one or more bytes, for instance '. ' (a period followed by a space) could be represented by byte 1, 'The' could be represented with byte 2, and 'Ishmael' could be represented by a 255 then a 7 (among many other sequence codings).

Challenge

Create a program that compresses a plain-text version of a work of literature by returning a byte-wise Huffman coding table and a sequence of bytes that represents the text with that table.

Rules and Assumptions

  • You may assume that the text is written in English and uses only printable ASCII characters plus space, newline, and tab.
  • It must be a proper Huffman coding; no mapping may be the prefix of another.
  • Not all Huffman sequences need to be mapped to a particular character sequence; you could, for instance, not have 7 mapped to anything or not have 255, 39 mapped to something, but have every other 1 and 2 byte sequence mapped to something.
  • The returned coding table must be able to encode every possible sequence of valid characters (as per the first assumption above). The simplest way to do this is to make sure that every individual character is mapped to a Huffman byte sequence.
  • It can be possible to encode a body of text multiple ways using the returned encoding table. If both ca and at are mapped to byte sequences, cat could be encoded two ways. This is totally fine.
  • Case must be preserved.
  • Runs do not need to be deterministic, i.e. two runs of the same program with the same input could produce different Huffman tables and compressed output.
  • Your program must return a result within a reasonable amount of time to be considered a valid solution. (If you want a hard limit, I'll say 5 minutes on a 2GHz Intel dual-core i5 with 16 GB RAM running Windows 10)

Scoring

Your results will be run against a corpus of (TBD) 12 publicly available literary (and non-fiction) works. For each work of literature, your score will be the size, in bytes, of the compressed text, plus the total length of all text strings mapped to a byte sequence in the Huffman-coding table. Your overall score is the total score across all 12 works.

Lowest score wins.

Literature list

  • The King James Bible
  • Hamlet by William Shakespeare
  • Dracula by Bram Stoker
  • Frankenstein by Mary Shelley
  • On the Origin of Species by Charles Darwin
  • Moby-Dick by Herman Melville
  • Little Women by Louisa May Alcott
  • Tom Sawyer by Mark Twain
  • Pride and Prejudice by Jane Austen
  • The Hound of the Baskervilles by Arthur Conan Doyle
  • < Something that entered the public domain in 2019 because it was published in 1923 >
  • < Something written in the last 20 years willingly released into the public domain or with a Creative Commons license that allows derivative works >

Sandbox

At least one of the last two literary works should preferably be written by a female and/or non-white author to hopefully make writing styles diverse enough to make hard-coded Huffman tables ineffective. Each work should be comparable in length to the other works.

Links to these books (in plain text) would be appreciated. Substitution suggestions are welcome.

\$\endgroup\$
8
  • \$\begingroup\$ If you want to vary writing styles, is there a non-fiction work that only contains the allowed characters? \$\endgroup\$ – trichoplax Sep 24 '19 at 23:21
  • \$\begingroup\$ @trichoplax The most notable non-fiction book I can think of for that would be "On the Origin of Species" by Charles Darwin. I've also thought about throwing in the King James bible. Maybe I could bump up the total to 12 works. I also probably will drop War and Peace because the plain text version I found was machine converted and has issues. \$\endgroup\$ – Beefster Sep 25 '19 at 15:21
  • \$\begingroup\$ Regarding plain text books, have you checked Project Gutenberg? They have plaintext versions of many of their books. \$\endgroup\$ – AdmBorkBork Sep 25 '19 at 18:35
  • \$\begingroup\$ I have no idea how much sample text is a good amount for this challenge (number of books, length of books) but it's probably worth doing some kind of rough check that there is enough text to give variation between answers (no optimal solution) while still being little enough text that running in a reasonable time is realistic (doesn't require weeks of work before an answer is efficient enough to meet the time restriction). Maybe others can suggest good ways of approximating this? \$\endgroup\$ – trichoplax Sep 25 '19 at 20:16
  • \$\begingroup\$ @trichoplax so basically you suggest sampling out, say, a few chapters instead of the whole book and then reducing the required runtime? I'm open to that, especially since the word count difference between Hamlet and the Bible is so big. The interesting thing about the Bible is that it has a ton of different authors, so it would almost be better to have the first chapter of each book instead of inserting, say, the entirety of Genesis. \$\endgroup\$ – Beefster Sep 26 '19 at 4:41
  • \$\begingroup\$ I couldn't guess at this point whether more text or less text would be better, and I don't have a way of estimating, just wondering if anyone else does. \$\endgroup\$ – trichoplax Sep 26 '19 at 7:32
  • \$\begingroup\$ I see no problem with 5 minutes as a rough time limit. I'd lean towards a time limit that allows someone to write a quick answer and then improve on it gradually, to encourage more participants. How long that needs to be for the text you settle on I don't know. As long as you're confident an optimal solution can't be found, you could just time a naive approach and then choose a time that doesn't exclude that. Then you can get lots of early answers to get the competition going, but still have open ended improvement over the long term \$\endgroup\$ – trichoplax Sep 26 '19 at 7:38
  • \$\begingroup\$ Not to say that this isn't an interesting challenge as it is but I do wonder if it wouldn't be more interesting without requiring that we use Huffman Encoding? \$\endgroup\$ – Shaggy Sep 27 '19 at 22:21
3
\$\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\$
6
  • \$\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\$ – DanielOnMSE Mar 9 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\$ – Redwolf Programs Mar 9 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\$ – DanielOnMSE Mar 9 at 5:28
  • \$\begingroup\$ @DanielOnMSE Ah, I see what you mean. I'll fix that. \$\endgroup\$ – Redwolf Programs Mar 9 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\$ – DanielOnMSE Mar 9 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\$ – Redwolf Programs Mar 9 at 13:21
3
\$\begingroup\$

What's the odd one out?

\$\endgroup\$
2
  • \$\begingroup\$ Looks like this but a bit more interesting \$\endgroup\$ – Razetime Mar 9 at 13:35
  • \$\begingroup\$ Great challenge! Seems ready to be posted \$\endgroup\$ – ophact Mar 9 at 16:03
3
\$\begingroup\$

Sociable sequences

\$\endgroup\$
8
  • \$\begingroup\$ You probably need to describe what a proper divisor is. Separately, I'm not sure how great requiring infinite output is. I'd probably consider allowing another optional argument that limits how many sequences to output? \$\endgroup\$ – FryAmTheEggman Nov 12 '20 at 19:47
  • \$\begingroup\$ @FryAmTheEggman I've updated the challenge to be closer to the normal [sequence] I/O rules \$\endgroup\$ – caird coinheringaahing Nov 26 '20 at 15:23
  • \$\begingroup\$ So is 25 a 1-sociable number, since its divisors sum to 6, and then there's a cycle? \$\endgroup\$ – user Jan 6 at 21:04
  • 1
    \$\begingroup\$ @user No, \$25\$ is not a \$1\$-sociable number. "They are numbers whose proper divisor sums form cycles beginning and ending at the same number". \$25\$'s "cycle" is \$25 \to 6 \to 6 \to \cdots\$, which does not begin and end with the same numbers. I'll edit that in though \$\endgroup\$ – caird coinheringaahing Feb 22 at 17:50
  • \$\begingroup\$ That "begin and end at the same number" is unclear. (it's a cycle, it neither begins nor ends) Perhaps "the initial number is inside the cycle". \$\endgroup\$ – user202729 Feb 24 at 4:30
  • \$\begingroup\$ Should that "given value" be interpreted as "value that will be given as input"? \$\endgroup\$ – user202729 Feb 24 at 4:31
  • \$\begingroup\$ That "does not diverge" sounds like a terribly hard conjecture... EDIT indeed it is. en.wikipedia.org/wiki/Catalan%E2%80%93Dickson_conjecture ("likely false"), and looks like that the sequence you came up with already have a name. \$\endgroup\$ – user202729 Feb 24 at 4:32
  • \$\begingroup\$ with that, it's problematic, you'd better specify that "If there are \$ n \$ such numbers, the answer must provably finish printing them all without assuming the conjecture" -- although for most approaches it isn't that hard. \$\endgroup\$ – user202729 Feb 24 at 4:38
3
\$\begingroup\$

Write an interpreter generator

\$\endgroup\$
14
  • \$\begingroup\$ Can an input contain one or more operations? like a + 1 - 4 * 8? Is input guaranteed to be valid? \$\endgroup\$ – Wasif Mar 22 at 17:11
  • \$\begingroup\$ @Wasif editing the answer \$\endgroup\$ – ophact Mar 22 at 17:12
  • \$\begingroup\$ Another suggestion, you might make it a code-challenge, where the objective will be to generate as short output as possible (Which means to golf the generated interpreter as much as possible), where the original source code length will not matter, so people can work for their code more peacefully, But code-golf (original challenge) one is good too. \$\endgroup\$ – Wasif Mar 22 at 17:14
  • \$\begingroup\$ @Wasif hmm... not a bad idea at all. This challenge does seem more effective with the code-challenge tag, I will edit that into the answer. \$\endgroup\$ – ophact Mar 22 at 17:17
  • \$\begingroup\$ @Wasif on second thought, I'm not really sure how you would actually test the length of the output... it would not be fair for one answerer to test with a 100-command language while another tests with a simple 1-command language. Thanks for the suggestion, but code-golf seems like the better option for now. \$\endgroup\$ – ophact Mar 22 at 17:19
  • \$\begingroup\$ OK, also how would handle destructive input like a / 0, which attempts to divide the accumulator by 0, which would result into crashing the interpreter? \$\endgroup\$ – Wasif Mar 22 at 17:22
  • \$\begingroup\$ the input is valid doesn't seem like a good enough description, let me change that \$\endgroup\$ – ophact Mar 22 at 17:22
  • \$\begingroup\$ "each command is one letter long." so, highest number of inputs are 26? \$\endgroup\$ – Wasif Mar 22 at 17:33
  • \$\begingroup\$ Can we pre-define the input array in the header section of Try It Online? \$\endgroup\$ – Wasif Mar 22 at 17:35
  • \$\begingroup\$ @Wasif yes, that can be inferred from that fact. Not sure what the header is, because I don't really use tio \$\endgroup\$ – ophact Mar 23 at 6:23
  • \$\begingroup\$ Header section means the part where you write code, is not added to the byte count. \$\endgroup\$ – Wasif Mar 23 at 6:52
  • \$\begingroup\$ Let us continue this discussion in chat. (Automatically comments were moved there because lengthy conversations cannot be run in comments) \$\endgroup\$ – Wasif Mar 23 at 6:52
  • \$\begingroup\$ I've edited this to a stub now that it's been posted \$\endgroup\$ – caird coinheringaahing Mar 23 at 15:40
  • \$\begingroup\$ @ChartZBelatedly thank you, forgot to do that \$\endgroup\$ – ophact Mar 23 at 16:05
3
\$\begingroup\$

Keep PPCG running in Game of Life

\$\endgroup\$
5
  • \$\begingroup\$ "Minimally destroying CGCC", "Keep PPCG running". Hmm, someone doesn't like the name change :). May I ask why you have this proposal too, though? \$\endgroup\$ – user Mar 22 at 19:24
  • 2
    \$\begingroup\$ @OriginalOriginalOriginalVI Because the two tasks are different, and I very much doubt answers to the two will be trivially similar \$\endgroup\$ – caird coinheringaahing Mar 22 at 19:38
  • \$\begingroup\$ Right now you could just place a glider in the box and it would run forever. Maybe redefine 'fixed position'? \$\endgroup\$ – A username Mar 23 at 8:16
  • \$\begingroup\$ @Ausername "If any spaceships or patterns of infinite growth are generated, the board will never reach a "fixed state" and such cases are invalid submissions." A glider is a spaceship \$\endgroup\$ – caird coinheringaahing Mar 23 at 13:13
  • \$\begingroup\$ Oh ok, didn't see that bit. \$\endgroup\$ – A username Mar 23 at 19:37
3
\$\begingroup\$

Limit of lists

You're given a never-ending sequences of lists, each of which appends some number of values to the end of the previous one. That is, each list is a prefix of the next.

3
3,1,4
3,1,4,1
3,1,4,1
3,1,4,1
3,1,4,1,5,9,2,6
...

While some steps may leave the list unchanged, its length grows unboundedly, giving an infinite list in the limit. Your goal is to output this infinite list.

Note that you can't know a-priori how many lists you must read to get, say, the 5th value in the infinite list, just that you'll eventually hit a list with 5 or more elements.

Input and output:

The list elements are digits 0-9. You may treat them as characters if you wish.

The input and output are both infinite lists. These can be represented in various ways, and may be different for the input and output.

  • An infinite list or stream
  • A stateful method or black-box function that produces a new value with each call
  • Repeatedly reading from STDIN or writing to STDOUT, or file buffers or the like

A mapping from index to value isn't allowed for input or output. The output must be uniform, without chunks of digits grouped together.


Sandbox: Infinite list I/O is hard. Any suggestions?

\$\endgroup\$
3
  • \$\begingroup\$ "Your goal is to output this infinite list" - can you clarify that it's by taking later elements from the lists that get later and later in the input list - I had to read this several times to understand that. Also, while I don't think there's any getting around the infinite input requirement, perhaps you could change the output to standard sequence rules to make it more flexible? \$\endgroup\$ – pxeger Mar 27 at 18:04
  • \$\begingroup\$ Is the first list guaranteed to be one element long? Or can it be any length? Can it (and any subsequent lists) be empty? \$\endgroup\$ – pxeger Mar 27 at 18:09
  • \$\begingroup\$ You should probably specify the intermediate output/s needs to be as soon as it's available from the input infinite lists, or at least in finite time, so noone can submit tail -1 \$\endgroup\$ – pxeger Mar 27 at 18:21
3
\$\begingroup\$

cadaddadadaddddaddddddr - linked list accessing

\$\endgroup\$
8
  • \$\begingroup\$ Yay, a lisp challenge! Does each 'a' mean a car and each 'd' a cdr? \$\endgroup\$ – user Mar 24 at 21:56
  • 1
    \$\begingroup\$ @OriginalOriginalOriginalVI yeah, but I'm to lazy to have written a description in english so far. I guess I'll get to it eventually :P \$\endgroup\$ – Wezl Mar 24 at 21:58
  • \$\begingroup\$ Fortunately the common lisp hyperspec already describes the bulk of it well. \$\endgroup\$ – Wezl Mar 24 at 22:22
  • \$\begingroup\$ You might want to make the reference implementation a link to TIO (unless it doesn't work on TIO, of course) \$\endgroup\$ – user Mar 24 at 22:23
  • \$\begingroup\$ @OriginalOriginalOriginalVI Why? (I can't access TIO anyway) \$\endgroup\$ – Wezl Mar 24 at 22:25
  • \$\begingroup\$ Meh, I just don't like those code snippets, and it makes it easier to pull out of the question, modify the input, and stuff. These code snippets sometimes break for me. If you can't access TIO, though, it doesn't matter, of course. \$\endgroup\$ – user Mar 24 at 22:26
  • \$\begingroup\$ posted \$\endgroup\$ – Wezl Mar 25 at 15:04
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted \$\endgroup\$ – caird coinheringaahing Mar 28 at 14:01
3
\$\begingroup\$

Reverse Zip Bomb

Posted to main (2021-03-29)

\$\endgroup\$
9
  • \$\begingroup\$ Does the compression have to be lossless? \$\endgroup\$ – water_ghosts Mar 27 at 1:04
  • 1
    \$\begingroup\$ Is the “common compression algorithm” defined by the spec or the implementation? If I find a gzip implementation with a bug that produces unbounded output, is that a valid solution? And if it’s not valid, then if I use my computer’s built-in gzip, do I have to verify that it complies with the spec? \$\endgroup\$ – water_ghosts Mar 27 at 1:29
  • \$\begingroup\$ @water_ghosts It depends. I think anything like that would be handled on a case by case basis. I'd expect bugs in the (official or widely used) implementations of common compression algorithms to be quite rare. The compression doesn't have to be lossless, within what's reasonable (JPEG would be allowed, for example) \$\endgroup\$ – Redwolf Programs Mar 27 at 1:54
  • 2
    \$\begingroup\$ "common compression algorithm" isn't clear enough IMO. You should either allow any and all compression algorithms (so long as an implementation exists, perhaps before the challenge) or specify an exact list people can choose from \$\endgroup\$ – caird coinheringaahing Mar 27 at 16:15
  • \$\begingroup\$ I think well-known enough to have a Wikipedia article (or part of one) written about them is clear (I'll reword it to make it clear that there should actually be an article for it), any specific things you'd recommend changing about it? \$\endgroup\$ – Redwolf Programs Mar 27 at 16:56
  • \$\begingroup\$ Certainly interesting, but there doesn't seem to be any codewriting involved. \$\endgroup\$ – Alex bries Mar 27 at 17:09
  • \$\begingroup\$ @Alexbries I think it'd be allowed, since it's fairly similar to "find the password" type CnRs. IMO, although you're not writing Python or JS, you could still sort of consider it "writing in gzip" or "writing in png" since you're trying to find an input that gets "compiled" into a larger output. \$\endgroup\$ – Redwolf Programs Mar 27 at 17:16
  • \$\begingroup\$ @Alexbries Answers don't always have to be code \$\endgroup\$ – caird coinheringaahing Mar 27 at 17:25
  • \$\begingroup\$ I think specifying about a Wikipedia page should be enough @RedwolfPrograms \$\endgroup\$ – caird coinheringaahing Mar 27 at 17:26
3
\$\begingroup\$

Un-pipe an Elixir expression

\$\endgroup\$
5
  • \$\begingroup\$ It's unclear what kind of expressions we have to deal with, but it looks good, and interesting . E.g. do we have to handle expr |> function(with_one_parameter)? \$\endgroup\$ – Wezl Mar 25 at 15:27
  • \$\begingroup\$ @Wezl I was thinking the expression could be anything with printable non-whitespace ASCII but I realize now that could be problematic. I'll change it to be more restrictive. \$\endgroup\$ – 79037662 Mar 25 at 15:30
  • \$\begingroup\$ @Wezl I specified that you may assume all functions will take only one parameter, so you do not have to handle expr |> function(with_one_parameter). \$\endgroup\$ – 79037662 Mar 25 at 15:39
  • 1
    \$\begingroup\$ Why do some piped expressions have () and some do not? Are we meant to support both of these? \$\endgroup\$ – A username Mar 26 at 4:45
  • \$\begingroup\$ @Ausername It's to demonstrate that both are valid, but as I state in the rules you need only support one convention. \$\endgroup\$ – 79037662 Mar 26 at 13:17
3
\$\begingroup\$

What's my TIO uniqueness?

\$\endgroup\$
9
  • \$\begingroup\$ Oops, didn't read that \$\endgroup\$ – user Mar 23 at 20:59
  • \$\begingroup\$ Maybe you could say "undefined" instead of 0 in the sentence "The TIO uniqueness of a language for which this is impossible is 0". Also, do you want submissions to store all 680 language names in the code? \$\endgroup\$ – Bubbler Mar 24 at 23:58
  • 1
    \$\begingroup\$ @Bubbler Changed to undefined, it fits better. Yes, submissions should have some way of storing the names, be it in an external file or in the program itself etc. \$\endgroup\$ – caird coinheringaahing Mar 25 at 0:02
  • \$\begingroup\$ @FryAmTheEggman Given that there are 680, I think it may be impractical to include the full list in the question, which is why I linked to this gist with all languages and their outputs \$\endgroup\$ – caird coinheringaahing Mar 25 at 0:20
  • \$\begingroup\$ Ah, sorry, I missed the link. \$\endgroup\$ – FryAmTheEggman Mar 25 at 3:44
  • \$\begingroup\$ "subsequence" tag? Why? \$\endgroup\$ – tsh Mar 29 at 8:58
  • 1
    \$\begingroup\$ @tsh Because the TIO uniqueness depends on the shortest substring that isn't common with any other language \$\endgroup\$ – caird coinheringaahing Mar 29 at 18:49
  • \$\begingroup\$ but substring is not subsequence \$\endgroup\$ – tsh Mar 30 at 0:32
  • \$\begingroup\$ @tsh No, but [substring] isn't a tag, and [subsequence] is the best alternative \$\endgroup\$ – caird coinheringaahing Mar 30 at 21:37
3
\$\begingroup\$

Rejecting invalid IPv4 addresses

\$\endgroup\$
4
  • \$\begingroup\$ You should generally include the definition of things like this directly in the challenge rather than just linking to a Wikipedia article on it, so people don't have to go to an external site \$\endgroup\$ – pxeger Apr 8 at 8:42
  • \$\begingroup\$ I think it would be clearer if you used boolean true/false for "is this valid", rather than "invalid" vs "valid". You might also want to change classification to decision-problem \$\endgroup\$ – pxeger Apr 8 at 8:46
  • \$\begingroup\$ @pxeger Thanks. Included both suggestions. \$\endgroup\$ – rsjaffe Apr 8 at 15:55
  • \$\begingroup\$ Is this means the input should always be a string / list of characters? May I take input as an array of 4 integers / a 32 bit unsigned integer / a built-in type for IP address (if there is one)? \$\endgroup\$ – tsh Apr 13 at 3:57
3
\$\begingroup\$

Remove first encountered elements from a second list

\$\endgroup\$
8
  • 1
    \$\begingroup\$ While this comes from an SE question, having two arrays seems a bit odd. A more standard task is simply to remove the first occurrence from the single array. (Though, it may be a duplicate then) \$\endgroup\$ – Nathan Merrill Aug 17 '16 at 18:33
  • \$\begingroup\$ @NathanMerrill I thought of limiting it to just one array, but in my opinion this way is more challenging. \$\endgroup\$ – pajonk Aug 17 '16 at 19:01
  • \$\begingroup\$ I agree, it does increase the difficulty of the challenge. \$\endgroup\$ – Nathan Merrill Aug 17 '16 at 19:04
  • 1
    \$\begingroup\$ The separator between the elements of the list needs to be distinct from the separator between lists -- it just means that the two output lists should be distinguishable (and not clumped into a single list, for example), right? The current wording doesn't make much sense if we can return two lists from a function. \$\endgroup\$ – Bubbler Apr 12 at 23:07
  • \$\begingroup\$ @Bubbler, yes, that's right - I'll change it. Thanks. \$\endgroup\$ – pajonk Apr 13 at 5:06
  • 1
    \$\begingroup\$ I suggest using standard JSON in your examples, e.g. [2,3,3,5,5,4,3,7,1] \$\endgroup\$ – Adám Apr 13 at 6:58
  • 2
    \$\begingroup\$ I think removing elements from L2 is unnecessary. The essence of the challenge is to remove elements from L1 based on the first occurrence of each unique element in L2. \$\endgroup\$ – Adám Apr 13 at 7:00
  • \$\begingroup\$ Thanks @Adám for the comments. You're right - I edited accordingly. \$\endgroup\$ – pajonk Apr 13 at 19:41
3
\$\begingroup\$

Interpret control characters like a terminal

\$\endgroup\$
4
  • \$\begingroup\$ As "your program does not need to interpret backslash escape sequences - the input will contain the literal control codes themselves.", I'd suggest actually including the characters in the test cases, or at least including a TIO link (or pastebin etc.) with the literal characters \$\endgroup\$ – caird coinheringaahing Apr 12 at 13:14
  • 1
    \$\begingroup\$ @cairdcoinheringaahing \r isn't really usable on the web because it will be converted to a newline, and most languages have their own literal syntax for entering those characters anyway, so I think it wouldn't really help \$\endgroup\$ – pxeger Apr 12 at 13:18
  • 1
    \$\begingroup\$ Suggest a aaaaaaa\b\b\b\t case, do TAB fill them space? \$\endgroup\$ – l4m2 Apr 15 at 4:17
  • \$\begingroup\$ @l4m2 thanks - that helped me discover some subtle bugs in my reference implementation too \$\endgroup\$ – pxeger Apr 15 at 9:01
3
\$\begingroup\$

You are kinda Replacable to Me

\$\endgroup\$
3
\$\begingroup\$

A Self-Referential Sentence

The Story


One day, you decide that you want a sentence that tells you where in the sentence the letter T occurs (excluding whitespace and punctuation). Out of curiosity, you try to make one. Messing around a little you get

T is the first, fourth, eleventh, sixteenth, twenty-fourth, ....

Oh dear, this sentence appears to run forever. But you now think you have an interesting number sequence, so you slap it into the OEIS search bar and lo and behold you find sequence A005224, Aronson's sequence. And better yet, an interesting code-golf problem that no appears to have posed before!


The Task

Your task is to write a program that takes in a single positive integer, n, as input and gives the position of the n-th "t" in the above sentence (indexing begins at 1 for the sake of this problem). For example, an input of 1 should return 1, while 2 should return 4. The input number will not exceed 4 decimal digits in length (i.e. the maximum input is 9999)

As always, the shortest code in bytes wins, and standard loopholes apply.


Tags:


The Meta

Ok, so I have a couple of questions, since this my first sandbox post.

  1. What can I do to flesh out this problem? This seems short, especially for a CGSE prompt. Should I somehow flesh out the heading fluff? Or should I add something more to the task itself?
  2. I was pretty thorough in my search of the sandbox and main site for similar problems, but I could always have missed something, so please let me know if this is a duplicate.
  3. Is the 4 digit input limit reasonable? Should I raise it or lower it? Remove it entirely? Since I'm not providing a file with ordinal strings, it seems like having a restriction on the size of the input is quite important.
  4. Finally, please let me know if there's any other glaring problems in this prompt, this is both a first draft, and my first attempt at a code-golf prompt (since high-school).
\$\endgroup\$
3
  • \$\begingroup\$ Nice first challenge! I'd suggest following the standard sequence I/O rules and allowing programs to output either the first \$n\$, the \$n\$th term or all terms. Additionally, forcing 1-indexing (for the sequence) doesn't improve the challenge any more than allowing either 0 or 1 indexing. I cannot find any challenge that could be a dupe through some searching, so this looks to be 100% original. Finally, I'd recommend including either test cases or the first 10 or so terms in the challenge body \$\endgroup\$ – caird coinheringaahing Apr 24 at 16:21
  • 1
    \$\begingroup\$ @cairdcoinheringaahing 1-indexing is fundamental to the recursive definition of this sequence, as “T is the zeroth, third, tenth, twelfth, seventeenth, twentieth, …” is quite a different sequence (not just off by one). \$\endgroup\$ – Anders Kaseorg Apr 25 at 18:25
  • \$\begingroup\$ @AndersKaseorg I meant 0 indexing in the input, not in the position of the T (e.g. n = 0 would output 1, n = 1 would output 4, etc.) \$\endgroup\$ – caird coinheringaahing Apr 25 at 18:27
3
\$\begingroup\$

diddly darn posted

\$\endgroup\$
10
  • \$\begingroup\$ Tag chess? \$\endgroup\$ – pxeger Apr 12 at 6:43
  • 1
    \$\begingroup\$ My god, this is amazing. I can't wait to see the full version! \$\endgroup\$ – StackMeter Apr 12 at 9:48
  • 1
    \$\begingroup\$ It's not clear to me what should be output in the non-deterministic cases. Do we have to output all possibilites? \$\endgroup\$ – kops Apr 22 at 23:35
  • \$\begingroup\$ Addtionally, what do you want the result of this to be: ,v, \n >,A \n ^<B (pastebin; is multline code possible in a comment?) Rules as written I think it's a tie since the center cell is reached twice but it's not clear this is desirable. \$\endgroup\$ – kops Apr 22 at 23:37
  • \$\begingroup\$ @kops it's okay for the board to result in a tie. \$\endgroup\$ – lyxal Apr 22 at 23:43
  • \$\begingroup\$ And the point is to output the result of the board, which may not be deterministic \$\endgroup\$ – lyxal Apr 22 at 23:43
  • \$\begingroup\$ So each possibility has to be output with the correct probability in the non-deterministic cases? And for the specific board in my second comment, it's very much morally an A victory, not a tie, but the technicality of passing through the same cell going in different directions makes it a tie in these rules which I find a bit weird. \$\endgroup\$ – kops Apr 22 at 23:46
  • \$\begingroup\$ @kops no it is not the probability but the result of running it once. That result may vary. And even though that may seem like it should be a win for A, it could be the result of some clever play from B to trick A into thinking they've won \$\endgroup\$ – lyxal Apr 22 at 23:50
  • \$\begingroup\$ @Lyxal I didn't mean to say the probability itself should be output, but that for each possibility, the probability of that possibility being output has to be correct? \$\endgroup\$ – kops Apr 22 at 23:56
  • \$\begingroup\$ @kops you only ever output one result - the winner of the game when evaluated. Because there are commands that change the direction, it can be impossible to 100% tell who wins. I was simply pointing out that there is more than one possible output for such boards. \$\endgroup\$ – lyxal Apr 22 at 23:59
3
\$\begingroup\$

Interpret Gelatin

\$\endgroup\$
3
\$\begingroup\$

CDGLF:TMN2APL


Meta questions:

  • Is this a duplicate? (I've looked and there are several challenges with operator precedence, but there are large differences such as floor/ceiling and the output format)
  • How can I objectively define "equivalent expressions"? Should I write a reference interpreter or answer?
  • Would it be more interesting going the other way?
  • Should answers be required to reject invalid input? Seems not
  • Should I I've replaced the unicode operators ×÷⌈⌉⌊⌋ with ascii symbols */{}[].
  • Is the exponentiation operator necessary? (It might just make the challenge more cumbersome because of its different associativity)
\$\endgroup\$
6
  • \$\begingroup\$ It was previously APL2TMN. I'm changing it to TMN2APL to make it more interesting. \$\endgroup\$ – Wezl Apr 22 at 14:42
  • 1
    \$\begingroup\$ TMN's +-×÷ are left-associative, but in APL everything is right-associative. The equivalent of TMN 3-5÷2+1 in APL is (3-5÷2)+1; APL 3-(5÷2)+1 is 3-((5÷2)+1). \$\endgroup\$ – Bubbler Apr 22 at 23:41
  • 1
    \$\begingroup\$ Thanks, I completely forgot about associativity. I don't think my grammar handles it, however, so I'm not sure exactly how to resolve this. \$\endgroup\$ – Wezl Apr 22 at 23:44
  • 1
    \$\begingroup\$ Also, I suggest to state the output format (APL) in the same way as you did for the input format (TMN), and state the precedence and associativity (for both TMN and APL) separately in plain English for those who are not familiar with parser grammars. And I think input validation is unnecessary here. \$\endgroup\$ – Bubbler Apr 22 at 23:52
  • \$\begingroup\$ I think the Unicode operators definitely should be replaced with ASCII, because otherwise it's 10 bytes used on every answer. This would require you to remove or change the output syntax of exponentiation, but I don't really feel like it adds much tbh. \$\endgroup\$ – pxeger Apr 24 at 15:57
  • 1
    \$\begingroup\$ @pxeger I've changed it, and I agree. \$\endgroup\$ – Wezl Apr 25 at 0:53
3
\$\begingroup\$

Turn-based RPS Poker

This is a two-player card game which resembles a vastly simplified game of Texas Hold'em, combined with RPS (rock-paper-scissors) and the most basic mechanic of commercial turn-based card games.

The deck

A single full deck consists of 30 unique cards, where each card has one symbol out of RPS and one number between 0 and 9 inclusive.

Since the 30-card deck is divided into three smaller decks during the game, let's call the 30-card deck a full deck (as opposed to simply deck).

The match

A single match consists of two phases: Draft phase and Main phase. In the Draft phase, the two players' decks (10 cards each) are decided. In the Main phase, actual games of Poker are played, and each player gets some score based on the number of games won.

Draft phase

  1. The full deck of 30 cards is shuffled.
  2. Repeat five times:
    1. Player A is given two cards from the top of the full deck.
    2. A picks one of them, which will go into A's deck.
    3. B gets the other card for B's deck, without knowing A's pick.
    4. Repeat 1)-3) with players A and B swapped.

At the end of Draft phase, players A and B have a deck of 10 cards each, and the main deck has 10 cards remaining. Additionally, each player gets to know 5 of the 10 cards in the opponent's deck during the process.

Main phase

  1. Each deck (player's and the remaining) is shuffled.
  2. Each player draws three cards from their own deck.
  3. Repeat 10 times:
    1. A card X is shown from the remaining deck.
    2. Each player plays a card from their own hand.
    3. A winner is determined by comparing (A's play + X) to (B's play + X). The winner gains 1 point.
    4. Each player draws a card from their own deck (unless there's nothing to draw).

Deciding the winner of a single game

The winner is decided by comparing the two-card combinations in the following order:

  1. If one combination is a pair (two cards sharing a number) and the other is not, a pair always wins against a non-pair.
  2. If the two cards played (excluding X) have different numbers, the player who played a higher-numbered card wins.
  3. Otherwise, the two cards are compared under the RPS rules. R wins against S, S wins against P, and P wins against R.

Note that a draw is not possible since every card is unique in a deck.

Bots and the controller

An answer should include a single bot that can handle the Draft phase and the Main phase.

TBD: detailed bot description (necessary methods for bots), an example bot, and the controller code coming soon.

Given multiple bots, the controller will run round-robin matches, and each pair of bots will be matched twice, once as A-B and once as B-A (in order to avoid possible bias due to the drafting order). The entire cycle will be run multiple times (exact number TBD) and all scores will be accumulated to decide the overall winner.


Meta

  • Does the game sound interesting? Is it too complicated? Would it be better if I remove the card-drawing mechanic (or any other part of the game, for that matter)?
\$\endgroup\$
3
\$\begingroup\$

Challenge Statement

The goal of this challenge is to build the 5 state Infinite Time Turing machine that takes the longest to halt.

The rest of this challenge is some definitions and an example to help you.

Turing Machines

For clarity we will define the Turing machines as used for this problem. This is going to be rather formal. If you are familiar with Turing machines this is a single-tape, binary Turing machine, without an explicit halt state, and with the possibility of a no shift move. But for the sake of absolute clarity here is how we will define a classical Turing machine and its execution:

A Turing machine consists of a \$3\$-Tuple containing the following:

  • \$Q\$: A finite non-empty set of states.
  • \$q_s : Q\$: The initial state.
  • \$\delta : Q\times \{0,1\} \nrightarrow Q\times \{0,1\}\times\{1, 0, -1\}\$: A partial transition function, which maps a state and a binary symbol, to a state, a binary symbol and a direction (left, right or no movement).

During execution of a specific Turing machine the machine has a condition which is a \$3\$-Tuple of the following:

  • \$\xi_\alpha : \mathbb{Z}\rightarrow \{0,1\}\$: The tape represented by a function from an integer to a binary symbol.
  • \$k_\alpha :\mathbb{Z}\$: The location of the read head.
  • \$q_\alpha : Q\$: The current state.

For a Turing machine the transition function takes the condition of a machine at step \$\alpha\$ and tells us the state of the machine at step \$\alpha + 1\$. This is done using the transition function \$\delta\$. We call the function \$\delta\$ with the current state and the symbol under the read head:

\$ \delta\left(q_\alpha, \xi_\alpha\left(k_\alpha\right)\right) \$

If this does not yield a result, then we consider the machine to have halted at step \$\alpha\$, and the condition remains the same. If it does yield a result \$\left(q_\delta, s_\delta, m_\delta\right)\$ then the new state at \$\alpha+1\$ is as follows:

  • \$\xi_{\alpha+1}(k) = \begin{cases}s_\delta & k = k_\alpha \\ \xi_\alpha(k) & k \neq k_\alpha\end{cases}\$ (That is the tape replaces the symbol at the read head with the symbol given by \$\delta\$)
  • \$k_{\alpha+1} = k_\alpha+m_\delta\$ (That is the read head moves left right or not at all)
  • \$q_{\alpha+1} = q_\delta\$ (That is the new state is the state given by \$\delta\$)

Additionally we define the condition of the machine at time \$0\$.

  • \$\xi_0(k)=0\$ (Tape is all zeros to start)
  • \$k_0=0\$ (Read head starts a zero)
  • \$q_0=q_s\$ (Start in the initial state)

And thus by induction the state of a Turing machine is defined for all steps corresponding to a natural number.

Infinite Ordinals

In this section I will introduce the concept of transfinite ordinals in a somewhat informal context. If you would like to look up a more formal definition this explanation is based of of the Von Neumann definition of ordinals.

In most contexts when talking about the order of events we use natural numbers. We can assign numbers to events such that events with smaller numbers happen earlier. However in this challenge we will care about events that happen after an infinite number of prior events, and for this natural numbers fail. So we will introduce infinite ordinals.

To do this we will use a special function \$g\$. The \$g\$ function takes a set of numbers and gives us the smallest number greater than all the numbers in that set. For a finite set of natural numbers this is just the maximum plus 1. However this function is not defined on natural numbers alone. For example what is \$g(\mathbb{N})\$, or the smallest number greater than all naturals. To create our ordinals we say

  • \$0\$ exists and is an ordinal.
  • If \$X\$ is a set of ordinals then \$g(X)\$ exists and is an ordinal.

This gives us the natural numbers (e.g. \$1 = g(\{0\})\$, \$2 = g(\{1\})\$ etc.) but also gives us numbers beyond that. For example \$g(\mathbb{N})\$, this is the smallest infinite ordinal, and we will call it \$\omega\$ for short. And there are ordinals after it, for example \$g(\{\omega\})\$ which we will call \$\omega + 1\$.

We will in general use some math symbols \$+\$, \$\times\$ etc. in ways that are not defined explicitly. There are precise rules about these operators, but we will just use them as special notation without definition. Hopefully their use should be clear though. Here are a few specific ordinals to help you out:

\$ \begin{eqnarray} \omega\times 2 &=& \omega+\omega &=& g(\{\omega + x : x\in \mathbb{N}\})\\ \omega^2 &=& \omega\times\omega &=& g(\{\omega \times x + y : x\in \mathbb{N}, y\in \mathbb{N}\})\\ \omega^3 &=& \omega\times\omega\times\omega &=& g(\{\omega^2\times x+\omega\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z\in \mathbb{N}\})\\ \omega^\omega &=& & & g(\{\omega^x\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z < \omega^x\})\\ \end{eqnarray} \$

If an ordinal is not the successor of another ordinal, meaning there is not a next smaller ordinal, we call that ordinal a limit ordinal. For example \$\omega\$, \$\omega\times3\$, and \$\omega^{\omega\times 2}+\omega^6\times 4\$ are all limit ordinals. \$3\$, \$\omega\times 5 + 12\$ and \$\omega^{\omega^\omega}+1\$ are not. Some authors will specify further that 0 is not a limit ordinal, we will be explicit about 0 when we talk about limit ordinals to avoid confusion.

Infinite Time Turing Machines

A classical Turing machine is equipped with a start status, and a way to get from one status to another. This allows you to determine the status of the machine at any finite step.

Infinite time Turing machines extend classical Turing machines to have a defined status non-zero limit ordinals as well. That is ordinals as defined above which are not the successor of any previous ordinal. This addition makes the condition of the machine defined at transfinite time as well.

Formal definition

For this we add an additional object to the machine's definition

  • \$q_l : Q\$: The limit state

And we define the condition of the machine at some limit ordinal \$\lambda\$ to be

  • \$\xi_\lambda(k) = \limsup_{n\rightarrow \lambda} \xi_n(k)\$
  • \$k_n = 0\$
  • \$q_n = q_l\$

\$\$

Example

Here we have a diagram of the current 2-state champion:

2-State champion If we want to calculate how long this takes to halt we can't just throw it into a computer and run it, rather we have to determine it by hand.

To start we follow the machine through it's normal execution. It starts at \$q_1\$ and we can see that from there it always moves to \$q_2\$ flipping the cell under the read-write head. So here it turns the cell on. Then since the cell is on it will transition back to \$q_1\$, turning the cell off and moving to the right. This puts us in the exact same condition as the start, except the read-write head has advanced by 1. So it will continue in this loop of flipping on bit on and off and moving to the right endlessly.

ANIMATION 1 HERE

Now that we have determined the behavior of the machine for all finite steps we can figure out the state at step \$\omega\$. Each cell is on for at most 1 step, before being turned off, and then it is never on again. So the limit supremum of each cell is \$0\$, and at step \$\omega\$ the tape is entirely empty.

So this means that after \$\omega\$ the machine just repeats its exact behavior, the condition at step \$\omega+n\$ is the same as the condition at step \$n\$. And this persists even after we hit another limit ordinal, \$\omega+\omega\$, the tape remains blank and just repeats the same behavior over and over.

ANIMATION 2 HERE

So we now have an accurate description of the machine for states of the form \$\omega\times n + m\$, and it doesn't halt for any of those steps. It just repeats the same infinite pattern an infinite number of times. So now we can look at the step after all the steps we have described. We take the next limit ordinal:

\$ g(\{\omega\times n + m : n\in \mathbb{N}, m \in \mathbb{N}\}) = \omega\times\omega = \omega^2 \$

Your first instinct might be that the tape will be completely empty again, since it was empty at every step \$\omega\times n\$. However with infinities instincts can be misleading, so we should look at the definitions carefully instead.

In order for a cell to be zero it must converge to zero. Since the only possibilities are zero and one, this means that for each cell there must be some step \$x\$ after which that cell is always zero. Previously since each cell was only turned on once that step was just the step after it was turned off.

Now if such a step were to exist for a cell \$k\$ it would be of the form \$\omega\times n + m\$, however we know that the cell will be turned on again some time during the \$\omega\times(n+1)\$ iteration. In fact it will be turned on at exactly step \$\omega\times(n+1) + 2k + 1\$.

So no cell (with a non-negative index) will converge to a stable value. Meaning that by the limit supremum all non-negative cells will be on at time \$\omega^2\$.

ANIMATION 3 HERE

So here we finally get some new behavior. With cell 0 on, the machine transitions to \$q_2\$ turning the cell off, and since \$q_2\$ doesn't have a transition for off cells the machine halts.

This gives us a total of \$\omega^2+1\$ steps until halting.

\$\endgroup\$
2
  • \$\begingroup\$ It'd be nice to link the ITTM paper. Also, showing an example ITTM and explaining its halting time (like your ⍵×⍵ 2-state ITTM) would be helpful. \$\endgroup\$ – user41805 20 hours ago
  • \$\begingroup\$ @user41805 I'm currently working on an explanation for my 2-state ITTM champion. But the animations are a bit time consuming. I meant to link some ITTM papers, so I will add those links when I finish the edit I am working on. Thanks. \$\endgroup\$ – Wheat Wizard 20 hours ago
2
\$\begingroup\$

Count Syllables

The goal of this challenge is to write a program that can count the syllables in a word as accurately as possible.

Input

On STDIN, your program will receive a number X followed by X lines, each containing a single word. Simple enough. (Should there be a limit on the size of X?) The words will come from this list.

4
challenge
to
count
syllables

Output

Your output should be to STDOUT and have X lines. On each line should be the number of syllables counted in that word.

2
1
1
3

Scoring

To score you program, it will receive a long secret list of words to test. All programs will receive the same list of words. For each word, the number of syllables that your program got wrong will be added to the score of the program. If it output a 4 or a 2 when the word had 3 syllables, then one point will be added. If it said a 15 instead of a 3, then 12 points will be added to the score. The lower the score, the better.

For example, if for the above input your program output 3 2 2 2 (which would be produced by a program that counts strings of vowels), then the program would receive a score of 2.

Rules

Your program should not access any external files (such as the word list). Also, your program should be no more than 5,000 bytes long (is this a reasonable limit?).

The winner will be the person whose program has the lowest score, therefor the most accurate syllable counter. The deadline for submissions is [some time at least a month away].

Suggestions

I am open to all constructive criticism. Is 5,000 bytes a reasonable limit for the program size? How long should the official scoring test be? How long should the deadline be?

\$\endgroup\$
10
  • 10
    \$\begingroup\$ This has one major flaw: the output is subjective. How many syllables do these words have? Every; victory; hierarchy; desire; oil; hour; poem. The only real way I see to work around this is for you to produce a marked-up version of the word list. \$\endgroup\$ – Peter Taylor May 29 '12 at 20:40
  • \$\begingroup\$ I was really worried about that, and I don't see a way around it. \$\endgroup\$ – PhiNotPi May 29 '12 at 20:42
  • 1
    \$\begingroup\$ I personally would love to see more language processing challenges. I agree with @PeterTaylor on the difficulty of some words. Perhaps taking a specific text(s) and identifying explicitly in the challenge which words will have how many syllables? \$\endgroup\$ – Gaffi Jun 8 '12 at 3:34
  • 2
    \$\begingroup\$ @PeterTaylor ...Or maybe you could filter ambiguous words out of the reference list? \$\endgroup\$ – user16991 Feb 8 '15 at 1:19
  • 1
    \$\begingroup\$ What's the point of the first line of input? \$\endgroup\$ – msh210 Apr 27 '16 at 20:05
  • 2
    \$\begingroup\$ If you provide a reference list, A hyphenated reference list, and hide a secret list which may or may not include members of the reference list, this would be a reasonable challenge \$\endgroup\$ – Rohan Jhunjhunwala Sep 17 '16 at 0:05
  • \$\begingroup\$ Do you plan to post this? If not, I'd be happy to adopt it. (If you don't respond within two weeks, by community standards, I'm allowed to do so.) \$\endgroup\$ – MD XF Aug 18 '17 at 3:20
  • \$\begingroup\$ The example of inaccurate program that would score 2 - did you mean to output 3 1 1 2 rather than 3 2 2 2? \$\endgroup\$ – Heimdall Nov 9 '17 at 18:31
  • \$\begingroup\$ A reference list could be dynamic: potential contestants can ask for words of their choice to be added to the list. They won't know what's on the secret list but will try to make their programs as accurate as possible (according to your syllable count) so they should always be able to ask for specific words they are not sure about. Of course, you could make it in different language. In my language, Slovene, it's much clearer how many syllables words have. How about Solresol, haha! \$\endgroup\$ – Heimdall Nov 9 '17 at 18:38
  • \$\begingroup\$ I am going to adopt this if you don''t respond \$\endgroup\$ – Christopher Dec 20 '17 at 16:48
2
\$\begingroup\$

Play Simple 2-Dimensional Minecraft

Recently I found this video of "HansLemurson" showing a computer that was built in minecraft, which runs minecraft. He is playing minecraft on a computer that was built in minecraft that is running on his computer. To be specific, it is a two dimensional version with an 8x8 grid of cells. There is gravity, block placement, and even jumping. It is worth noting that the computer is single purpose. The same person has built programmable computers, but making them single purpose allows the computer to be much smaller.

Details

The minecraft world is an 8x8 grid (one horizontal and one vertical dimension). The grid is comprised of either Xs (representing blocks) or empty spaces. The player is an X that is blinking on and off about once every second.

There are two modes in the game, controlled by a toggle switch. The first mode is movement. This is controlled by a WASD-like button arrangement. If the player chooses to move left/right/down, the computer checks to see if the space immediately in that direction is empty. If so, then the player moves into that space.

If the player chooses to move up, then the computer checks that the block underneath the player is solid. If so, then the player moves upward two units. Notice that this can propel the player into a solid block. If this happens, the player is obscured by the solid block, but can still move to an empty block next to him. When the player is inside on a solid block, the game continues as if the block isn't there, although the block is still there once the player leaves it.

After each move, the player falls down one unit if there is empty space there. This simulates gravity. This is also why moving up moves up two units, so that the gravity makes a net movement of up one unit. Gravity does not cause the player to fall all of the way to the ground, just one unit.

The second mode is block placement. In this mode, the same exact WASD buttons are used. Instead of moving the player, they toggle the state of the block in that direction. If the player presses "left" and there is a block there, then the block is destroyed. If there is not a block there, then a block is placed. Again after this move, the player is again subject to gravity. The blocks are not subject to falling.

Toggling the toggle switch does not count as a move, and does not invoke gravity.

The game board is a torus, so all actions (movement, block creation) can wrap around the board. The board does not scroll with the player. The player moves, and the blocks stay in the same place.

The challenge

You challenge is to write the shortest program that simulates this game. Your program should display and update the map correctly (with Xs as blocks, and with the blinking player). It should accept input from a button that toggles the state and four buttons for movement and actions. This is code golf.

There are imaginary bonus points for adding more features (block types, game size, etc) to your game.

Suggestions?

\$\endgroup\$
4
  • 2
    \$\begingroup\$ With more complicated challenges I find that it helps to do a reference implementation so that you have a very concrete idea of how much work is involved. Aside from that, I like it. \$\endgroup\$ – dmckee --- ex-moderator kitten Jun 3 '12 at 20:11
  • \$\begingroup\$ Is the blink rate selected to fit with the ANSI escape sequence? Either way I would explicitly allow that, because it's the obvious way to do it on compatible terminals. \$\endgroup\$ – Peter Taylor Jun 5 '12 at 7:14
  • \$\begingroup\$ The blink rate wasn't selected to be anything specific. I think that I will broaden the restriction. Maybe any blink rate between 3 blinks per second to 1 blink every 2 seconds. \$\endgroup\$ – PhiNotPi Jun 5 '12 at 20:21
  • \$\begingroup\$ @programmer5000 No, for two main reasons: First, challenges can go extended periods of time in the sandbox before they are posted and/or adopted. In the past I've posted challenges after not touching them for 4 years. Second, deleting this answer will not reduce lag, as deleted answers are still present, simply not visible. Users with sufficient rep will see all 4040 answers in the sandbox, and you will too once you earn the "view deleted answers" privilege. \$\endgroup\$ – PhiNotPi Apr 13 '17 at 18:15
2
\$\begingroup\$

Bad Voice Recognition Calculator

Overview:

Let's say you've decided to operate your computer using voice recognition software, but unfortunately you did a horrible job researching the various products out there and chose a package that does not recognize numbers as numerals, only words. (i.e. "one" (spoken) == "one" (typed), not "1".) Rather than spend more money to get another option, you decide to make do. Now you want to use the computer's calculator, but this poses a problem, since your machine doesn't know how to add "one plus one".

Objective:

Implement a basic calculator that will read in a string of the written-out equation, perform the correct calculations, then return the result in its text form. Your code should be as short as possible; this is code golf.

Rules/Constraints:

  • Input/output will be using your preferred method (STDIN, ARGV, etc.).
  • Your calculator must be able to handle input and output within the billions (non-inclusive) -1,000,000,000 < i < 1,000,000,000, but you may expand to more if you wish.
  • Decimal values and/or parts must be accepted (0 < i < 1) up to 3 places/digits.
    • When calculating answers, proper rounding must be used, so "three point one four one five nine two six" must be returned as "three point one four two".
  • Basic calculator functions required:
    • "Add"/"Plus"/"Sum"/"And" (+)
    • "Subtract"/"Minus"/"Remove" (-)
    • "Multiply"/"Times" (*)
    • "Divide"/"Divided"/"Divide by"/"Divided by" (/)
    • "Raise"/"Exponent"/"Power"/"To the power of" (^)
    • "<Base>Root"/"<Base>Radical" (√)
    • "Point"/"Decimal" (.)
    • "Pi" (π)
  • All strings in the list above must be accounted for in your code, capitalization does not matter.
  • Numbers may be presented as their full value ("one thousand") or by digit (one zero zero zero).
  • Negative numbers may be assigned using "Minus" or "Negative".
    • The string "Minus" bust be accounted for as an operator and identifier. (see example)
  • "And" is only acceptable as an operator, not as part of a named number.
    • "one hundred and one"
    • "one hundred one"
  • "a" or the absence of a number does not equate to any number; all numbers will be explicitly accounted for in the program input.
    • "a hundred" does not equate to "one hundred" and is not a valid input.
  • No more than 2 terms will be used.
    • "one plus one minus one" will not be implemented.
  • If an invalid input is supplied, your function/program should handle the error and exit gracefully with an error description.

Example I/O:

  • "one add one" --> "two"
  • "five thousand thirty four subtract ten thousand six hundred" --> "negative five thousand five hundred sixty six"
    • Alternatively: "five zero three four subtract one zero six zero zero"
  • "three root twenty seven" --> "three"
  • "ten minus minus ten" --> "twenty"
    • Alternatively: "ten subtract negative ten"

Sandbox Questions:

  1. Is this too basic/complicated? (I'm assuming some languages will handle this much more simply than the method I have in my head...)
  2. Does the title fit?
  3. Are there any constraints that should be added/lifted?
  4. Are any more examples needed for clarification?

Thanks for your input, guys!

\$\endgroup\$
6
  • \$\begingroup\$ Not everyone says numbers the same way. Does the parser have to treat the following as equivalent? "negative one hundred five", "minus one hundred five", "negative one hundred and five", "minus one hundred and five", "negative a hundred five", "negative a hundred and five", ...? \$\endgroup\$ – Peter Taylor Jun 15 '12 at 15:12
  • \$\begingroup\$ @PeterTaylor I had had a similar thought re: operators. ("plus" versus "add", etc.) I think it would be more interesting to account for all, but given the wide variety of possible inputs, it may generally be better to limit the options to a specifically defined set (which I have yet to define). \$\endgroup\$ – Gaffi Jun 15 '12 at 15:18
  • \$\begingroup\$ @PeterTaylor I've added some of these details. Please let me know if there's anything unclear about them. \$\endgroup\$ – Gaffi Jun 15 '12 at 16:10
  • \$\begingroup\$ I don't spot any ambiguities in the parser. There is still an ambiguity relating to decimals, though. What precision should be used? Also, I notice now that there's no winning condition. Is this intended to be code-golf? (Ugh - tons of strings which will have to be hard-coded in most languages. I expect Perl has a suitable parser already in CPAN, though...) \$\endgroup\$ – Peter Taylor Jun 19 '12 at 9:03
  • \$\begingroup\$ @PeterTaylor I don't know where I went... I've updated the spec. re: decimal places and objective. \$\endgroup\$ – Gaffi Jun 29 '12 at 13:24
  • 1
    \$\begingroup\$ @PeterTaylor metacpan.org/pod/Lingua::EN::Words2Nums \$\endgroup\$ – msh210 Apr 27 '16 at 20:37
2
\$\begingroup\$

Huffman Decoding

Write a programm which takes two strings as input and prints a text.


The first argument is a Huffman Tree, serialized in the following format:

  • every ascii character except ~ is always a leaf, if ~ is the first characater it is also a leaf.
  • <tree0><tree1>~ is a tree where <tree0> is the left subtree and <tree1> is the right subtree.

Example: ab~cde~~~ generates this tree:

 ┌─┴─┐
┌┴┐ ┌┴─┐
a b c ┌┴┐
      d e

where a would have the key 00, b 01, c 10, d 110 and e the key 111.


The second argument is a text that has been compressed with with the Huffman code that is defined by the first parameter. This bit-string can contain any bit sequence (also null-bytes and non-printable characters) and is not byte aligned, therefore it has been encoded with a variation of the standard Base64 encoding:

  • the characters used for the encoding are the standard base64 characters: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
  • the bitstring is broken up into 6-bit chunks and mapped to this characters
  • if the last chunk is smaller than 6 bits, a character with this prefix is used, and padding characters are added to the string:
  • - : the last chunk was five bits long
  • = : the last chunk was four bits long
  • =- : the last chunk was three bits long
  • == : the last chunk was two bits long
  • ==- : the last chunk was one bit long

Example:

bits:       1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1
chunks:    |1 1 1 1 0 1|1 0 1 0 0 1|1 1 0 1 0 1|0 0 0 1 1 0|1[0 0 0 0 0]|
characters:       9           p           1           G           g
base64:     9p1Gg==-

Your programm has to decode the text encoded in the second parameter and print it to stdout.

You have to provide your source code encoded in the way described above. The length of your encoded source code + the length of your serialized huffman tree will be the winning criterion.

TODO: example input

\$\endgroup\$
2
  • \$\begingroup\$ It would be helpful to explicitly state the 64 characters used in the encoding. I presume they're A-Za-z0-9+/ but (especially if you're expecting people to implement that part explicitly) it's best to make the problem self-contained. \$\endgroup\$ – Peter Taylor Oct 8 '12 at 16:23
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) \$\endgroup\$ – programmer5000 Jun 9 '17 at 15:30
2
\$\begingroup\$

Graphical Output -- Esoteric Artifacts -- The Glass Bead Game

Draw the Cabalistic Tree of Life

Simply described, the Tree of Life is an undirected network of nodes representing the conduit between matter and higher forms of spiritual energy. It has an upper face arranged in a hexagon, and a lower fact built from equilateral triangles adjacent to the lower two edges of the upper face. Don't label the paths, paths may overlap however you wish, may be single (thick) lines, even. Code Golf. Bonus -100 for labels on the Sephiroth (nodes); Bonus -150 for Hebrew labels.

Tree of Life after Kirtcher

Draw a Mandala for each Natural Number

Draw a circle with interesting visual patterns using the input N [ 1 .. \inf ) to determine the number of points around the circle to anchor figures whose shape is also modified by the input N. Actually, 12 seems like a good max: they're pretty much a blur after that no matter what.

Eg. http://code.google.com/p/xpost/downloads/detail?name=ve6a.ps
//lotsoflines n = 1 ..12

Mandalas 1 - 12

(doesn't need to be this elaborate, This is >600 lines of showing-off.).

. . . need good images for these . . .

Draw the Ptolemeic System of the Universe

All the stuff I could find is animated already. Maybe this one's done-to-death. :(

Update: Found good stuff on Alchemy. The "Keplar Platonic" model could be fun (3D and all). This one looks good, too. And this.

Draw the Pythagorean Monochord

aka pre-classical nomogram. I misplaced my Pythagoras books, I know I've got a picture somewhere.

This is the one I was thinking of.

But I think this one's even cooler

Draw the I-Ching Hexagrams in King Wen Sequence.

I suppose I need to implement this first to avoid copyright issues! :)

\$\endgroup\$
3
  • \$\begingroup\$ The I-Ching one would have to be in standard order to be remotely interesting, and then becomes as much about kolmogorov-complexity as graphical-output \$\endgroup\$ – Peter Taylor Nov 22 '12 at 21:24
  • \$\begingroup\$ For the others: images, please! \$\endgroup\$ – Peter Taylor Nov 22 '12 at 21:25
  • \$\begingroup\$ I've emailed the owner of the Alchemy pages asking for permission to use his copyrighted images. Awaiting response. \$\endgroup\$ – luser droog Jan 28 '13 at 8:25
2
\$\begingroup\$

DeCSS

It is known that the DVD Content Scrambling System can be deciphered with a rather short program (434 bytes of C, 472 bytes of Perl). Can you do better?

<< Test cases go here >>


I don't plan to include a more detailed spec, because it will just wind up duplicating some of the code. The test cases would be in the form of (key, link to data file, md5sum of the deciphered stream).

\$\endgroup\$
4
  • 2
    \$\begingroup\$ And the winning criterion is who is the first to get post from the courts? \$\endgroup\$ – celtschk Oct 3 '15 at 20:18
  • \$\begingroup\$ @celtschk, I think that would be unfair. Winning criteria shouldn't really depend on where people live... \$\endgroup\$ – Peter Taylor Oct 10 '15 at 20:56
  • 3
    \$\begingroup\$ I think you should at least explain the general concept of the spec. \$\endgroup\$ – Rohan Jhunjhunwala Aug 2 '16 at 22:53
  • \$\begingroup\$ This actually sounds interesting. @PeterTaylor Perhaps you could use (and link to) Charles Hannum's explanation of the algorithm and post this. (It would be fun to have it as a popularity contest for a program that looks like it's nothing DeCSS related, or a program that furthers the gallery's point about the text vs source code arbitrary distinction - but I don't know if popularity contests are popular any more!) \$\endgroup\$ – sundar - Remember Monica Jun 25 '18 at 8:25
2
\$\begingroup\$

Code golfing problem: Surface classification

The task: Given a surface-word reply with the classification of what surface it is.

Example 1: Input: aba'b' ----> Output: 1T

Example 2: Input: aabcb'c' ----> Output: 3P

Bounds on the problem: Since there are only 26 letters, there will never be more than that many labels. Additionally output should be in the form S,nT,mP for n,m positive integers.

Background: In the study of algebraic topology students are often presented with diagrams such as the one below. The represent instructions for how to assemble a surface. The assembly is prescribed as: if there are two edges labeled with the letter x then glue them together so that the arrows point the same direction. To make our job easy, topologists have discovered an algorithmic way to classify surfaces using 'words' assembled from these 'plane gluing-diagrams'.

enter image description here Choosing a corner arbitrarily (top right) and orientation (ccw) we read off the labels on the edges where an inverse appears wherever the arrow points against the orientation. In this case the 'word' that represents this plane model is given as abab.

A surface word is a string that contains the letters a,b,...,@ up to some letter @ and each letter is contained in it exactly twice. In the two occurrences of each letter: 0, 1, or 2 of them may be postfixed by a ' which I am considering using to represent 'inverse' (opposite orientation).

If in a surface word all letters appear twice: once without the ' and once with it (f.ex. ba'b'a) then we say that the surface the word represents is orientable. If a surface is orientable then it is necessarily the direct sum of n Tori for some non-negative integer n. If this condition doesn't hold (like in aab'b) then the surface represented is non-orientable: in this case it is the direct sum of m Projective Planes for some positive integer m.

Once you have found out if the reduced word is orientable or not, the final answer is given as follows. If orientable and number of unique letters in the reduced word is 1 then output should be S. Otherwise if the number of unique letters in an orientable word is n (it will be even) then the output should be sT where s = n/2. If the word is non-orientable then the output should be mP where m is the number of distinct letters in the reduced word.

The goal is to take as input some surface word, reduce it via reduction rules 1-6 and then classify it as a sphere, some number of connected tori, or some number of connected projective planes. Here are the 6 reduction rules where ~ represents 'reduces to':

Let M,A,B,C,D be surface words, x be a single letter, and juxtaposition represents concatenation:

  1. Cycle Rule: If M = AB then M ~ BA
  2. Flip Rule: M ~ M'
  3. Sphere Rule: Axx'B ~ AB
  4. Block Rule: ABC ~ ADC if B is a surface word and B ~ D by 1 or 2
  5. Cylinder Rule: If M = AxBCx'D, then M ~ AxCBx'D
  6. Möbius Rule: If M = AxBxC then M ~ AxxB'C ~ AB'xxC

I am looking for input on:

  • should this be code-golf or programming-challenge?
  • how would scoring work?
  • ???

If I feel satisfied with the question in a few days I'll post it to the site.

\$\endgroup\$
5
  • \$\begingroup\$ If, for each input, there is only one correct output, then it should probably be code-golf. The scoring criteria would then be source code length. \$\endgroup\$ – PhiNotPi Jun 8 '13 at 14:33
  • \$\begingroup\$ Yes, this is the case. In general however there is not a unique series of applications of the reduction rules for any given instance. \$\endgroup\$ – Kaya Jun 8 '13 at 16:21
  • \$\begingroup\$ I don't think the order of explanation is correct. You should explain reduction before talking about "the reduced word". And "reduce it via reduction rules" doesn't entirely make sense, because the rules are presented as equivalences rather than reductions, and most of them don't have a "natural" direction. \$\endgroup\$ – Peter Taylor Jun 10 '13 at 8:49
  • \$\begingroup\$ It's also occurred to me that you haven't defined the notation M'. Does it just consist of toggling the orientation of each token, or does it also reverse the entire string? And do you have test cases which between them force implementation of all of the reduction rules? \$\endgroup\$ – Peter Taylor Jun 11 '13 at 8:32
  • \$\begingroup\$ Good call on the string inverse, yes you have the right idea and I will make it clear. I have a lot of test cases from when I did a number of these computations by hand in a university course and (anecdotal experience) I am pretty sure that it is possible to force the use of all the reduction rules (except maybe 4 which is really just a meta-rule for convenience when doing proofs). Additionally you have alerted me to some concerns regarding the form of the proper output: it's definitely underspecified. I'll put some work into this today. \$\endgroup\$ – Kaya Jun 11 '13 at 14:04
2
\$\begingroup\$

Business Card Ray Tracer

I have no idea how to create a good code golf question!

See this description of a ray tracer with source code that fits on a business card. The author stopped when the code size was 1337 bytes.

http://fabiensanglard.net/rayTracing_back_of_business_card/index.php

Achieving identical output, optimise for minimum code size. Execution time is not relevant.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ I think what you have here is a straight ahead golf. All languages. You need only define the requirements. Do you want identical output or do you want "good output encompassing <list of features>"? \$\endgroup\$ – dmckee --- ex-moderator kitten Oct 6 '13 at 17:22
  • 1
    \$\begingroup\$ For a minimum feature list I'd suggest something like (1) it is ray tracer (2) supports point-like lights and shadow + ambient light (3) supports mirrored (implies reflection) and matte surfaces (3) all objects are sphere and overlaps are allowed. With no requirement for (a) anti-aliasing; (2) finite sized light sources; (c) atmosphere effect or (d) depth of field; or (e) tiling and gradients. Notice however, that the example supports at least (b), (d) and (e). \$\endgroup\$ – dmckee --- ex-moderator kitten Oct 6 '13 at 17:29
  • 1
    \$\begingroup\$ BTW--The one you linked can get a little bit more with #define Q return (R was already taken for the rand wrapper) and #define O operator. \$\endgroup\$ – dmckee --- ex-moderator kitten Oct 6 '13 at 17:33
  • 3
    \$\begingroup\$ I suggest reading the Teapot question in the sandbox Mk IV and the comments - it's not the same question, but some of the same issues are relevant, and it might give you ideas for improvements to the spec. \$\endgroup\$ – Peter Taylor Oct 6 '13 at 22:48
  • \$\begingroup\$ Yes. Read the teapot question for guidance. Ultimately I decided that one was too big, but we did get into some pertinent details. \$\endgroup\$ – luser droog Dec 1 '13 at 9:48
  • \$\begingroup\$ This sandbox post has had little activity in a while and little positive reception from the community. Please improve / edit it or delete it to help us clean up the sandbox. \$\endgroup\$ – programmer5000 Jun 9 '17 at 15:32
2
\$\begingroup\$

Count unique characters in text.

Given a string for input, output the unique non-whitespace characters in that string along with a count of their occurrences. The list should be sorted in ascending order of ASCII code.

Examples

Input:

Hello, World!

Output:

Character    Count
!            1
,            1
H            1
W            1
d            1
e            1
l            3
o            2
r            1

Input:

The quick brown fox jumps over the lazy dog.

Output:

Character    Count
.            1
T            1
a            1
b            1
c            1
d            1
e            3
f            1
g            1
h            2
i            1
j            1
k            1
l            1
m            1
n            1
o            4
p            1
q            1
r            1
s            1
t            1
u            1
v            1
w            1
x            1
y            1
z            1

The actual formatting (headers, spacing, etc) of the on-screen output is up to you. The only conditions are that it must be sorted in ascending order by ASCII code, and it must be easy to tell what represents a character from the string and what represents a count of a given character. (For example, given a string of 99999999, the output should be explicit so that it is not confused as saying I have 9 8s.)

Ultimate challenge (taken from here):

JKqdJg+oJgiowgyIJgkS+gyxJdeS+gyxJ4yoJdybJdioJdqIJ4kS+KwFJ4QS+gzYJg+ow4vIJ4yxvd+IJgy=+dv=JdQx+gzbJrzx24zYJgkxJ4qLJKQxJ4yxJKqx+KqdJKqdJg+oJgiowgyIJgkS+gyxJdeo24yxJm+xJdybJdioJdqIJKi=J4wF+dvS+gzYJg+ow4zYJ4yxvdy=J4i=+Kv=JdQo+KqxJrzdJKzYJgkxJ4qLJgkxJ4yxJKvSJ4qbJKqdJg+oJgiowgyIJgkdJgyxJdeo24yxJm+xJdybJd+oJd+S+dz=J4wF+dvS+g+SJg+ow4vIJ4yxJ4voJgy=+dv=+dzdJgqxJrzdJKzYJgkS+dweJKQxJ4yxJKvSJ4qbJKq=24yYJgiowgyIJgkdJgzdJryo24yxJm+d24zxJd+oJdqIJ4kS+KwFJ4QS+gzYJ4y=2gzYJ4yxJ4voJgy=+dv=+dzdJgqxJrzx24zYJgkS+dweJKQxJ4fK+dQSJ4qbJKq=24yYJgiowgyIJgkS+gzdJryS+gyxJ4yoJdybJd+oJd+S+dz=J4wF+dvS+gzYJ4y=2gvIJ4yxJ4voJgy=+dv=JdQo+KqxJrzx24zY+dzS+dweJKQxJ4yxJKqx+KqbJKq=24vbJdyowgyIJgkdJgzdJryS+gyxJm+d24zxJdioJd+S+dz=J4wF+dvS+gzYJg+ow4vIJ4yxJ4voJgy=+Kv=JdQx+gzbJrzx24zYJgkS+dweJgkxJ4yxJKvSJ4qdJKq=24yYJgiowgyIJgkdJgzdJryS+gyxJ4yoJdybJd+oJdqIJKi=J4wF+dvS+gzYJg+ow4vIJ4yxJ4v=J4i=+Kv=+dzdJgqxJrzx24zYJgkS+dweJgkxJ4fKJ4qx+KqdJKqdJg+SJdyowg+oJgkS+gyxJdeS+gyxJ4yoJdybJd+oJdqIJ4kS+KwFJ4QS+g+SJ4y=2gzYJ4yxJ4v=J4i=+Kv=JdQo+KqxJrzx24zY+dzS+dweJKQxJ4yxJKvSJ4qbJKqdJg+oJgiowg+oJgkS+gzdJryo24yxJ4yoJdybJdioJdqIJ4kS+KwFJ4QS+g+SJg+ow4vIJ4yxvd+IJgy=+dv=JdQo+KqxJrzdJKzY+dzxJ4qLJKQxJ4yxJKqx+KqdJKq=24vbJdyowg+oJgkS+gzdJryo24yxJ4yoJdybJdioJd+S+dz=J4wFJ4QS+gzYJg+ow4zYJ4yxvd+IJgy=+Kv=+dzdJgqxJrzdJKzYJgkxJ4qLJgkxJ4yxJKvSJ4qbJKq=24vbJdyowgyIJgkdJgyxJdeo24yxJm+xJdybJd+oJdqIJKi=J4wF+dvS+g+SJ4y=2gvIJ4yxvd+IJgy=+dv=+dzdJKzbJrzdJKzY+dzS+dweJgkxJ4yxJKvSJ4qbJKq=24yYJgiowg+oJgkS+gyxJdeo24yxJ4yoJKzxJd+oJdqIJKi=J4wF+dvS+gzYJg+ow4vIJ4yxJ4v=J4i=+dv=+dzdJgqxJrzx24zYJgkxJ4qLJKQxJ4fKJ4qx+KqdJKqdJg+oJgiowgyIJgkS+gzdJryS+gyxJm+d24zxJd+oJdqIJKi=J4wFJ4QS+gzYJ4y=2gzYJ4yxvdy=J4i=+Kv=+dzdJKzbJrzx24zY+dzxJ4qLJKQxJ4yxJKqx+KqdJKqdJg+SJdyowg+oJgkdJgzdJryo24yxJm+d24zxJd+5

\$\endgroup\$
5
  • \$\begingroup\$ This isn't really an interesting problem. The shortest answer is almost certainly going to be fewer than 10 characters. \$\endgroup\$ – Peter Taylor Dec 11 '13 at 12:19
  • \$\begingroup\$ @PeterTaylor While I mostly agree with your comment - already the header line may contain more than 10 characters. \$\endgroup\$ – Howard Dec 12 '13 at 6:15
  • \$\begingroup\$ "The quick brown fox jumps over the lazy dog." contains "e" three times. \$\endgroup\$ – Howard Dec 12 '13 at 6:16
  • \$\begingroup\$ @Howard Thanks. I must be blind - it took me about five times of reading your comment to find it. Also, do remember that the header is optional to a certain degree - you just need to make sure the output is unambiguous as to which items are characters from the string, and which are character counts. \$\endgroup\$ – Iszi Dec 12 '13 at 7:02
  • \$\begingroup\$ My brain instantly went into bash mode. wc and uniq practically solve half of this, but not in any particularly short manner. \$\endgroup\$ – Rob Dec 17 '13 at 20:31
1
14 15
16
17 18
110

You must log in to answer this question.

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