Implement the random Fibonacci sequence

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

Quickly! Group together!

Is it a vampire number?

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?

code-golf brainfuck

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.$/ \!$/'?))='%<\..> 

KoTH: Hunter-Gatherer Society

king-of-the-hill, javascript, grid

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

Liars and Guessers

Self-Replicating Numbers

Minimally destroy CGCC in Game of Life

Posted

Two Diehards Make a Glider

game-of-life code-challenge source-layout

---

POSTED

I'm Jelly of Python (Cops)

I'm Jelly of Python (Robbers)

Decode Polybus Square/Tap Code/Prison Code

posted

Drop some boxes

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.

Open or close?

Posted here.

Convert prefix to infix

Minimum number of changed tiles to permit knight passage

code-golf path-finding

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))

Is it a fibonacci-like sequence?

Fibonacci triangle

Gray code on N symbols

Building spikes

Resolve references in a chat discussion

Pairs of integers ordered by their exponentiation

Convert between graph representations.

Satisfy as many people as possible

Posted here.

Unshuffle my poker chips

Storing a band matrix

BitCycle Metagolf