464
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 '19 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – S.S. Anne Sep 26 '19 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 '19 at 13:43

2665 Answers 2665

2
\$\begingroup\$

Create a block maze solver AI

A block maze is a maze in which goal is to complete a pathway by adding blocks.

It starts like this :

#..#.
#...#
..###
.#...
.#..#

# is a block (which can be crossed). . is empty space (which cannot be crossed).

The goal is to connect top-left corner S to the bottom-right corner E. Diagonals are not allowed.

S....
.....
.....
.....
....E

One possible solution for the example above is to add three blocks like this :

#..#.
#...#
#####
.#..#
.#..#

Think about a man who want to cross a river with crocodiles . using huge stone blocks #.

The task is to create a program that take a grid as input and return a solution as output.

Scoring

The sum of all blocks required to solve all solutions in a 1.000 test case file I will provide.

The winning program is the one that use the fewest blocks to solve all mazes.

Rules

  • All grids are 25 x 25.
  • Start / end points are always top-left / bottom-right corners. There is always a block on those points.
  • There is always one guaranteed solution (which can be found by filling all empty spaces)
  • Program must be entirely deterministic; pseudorandom solutions are allowed, but the program must generate the same output for the same test case every time. If two programs take the same number of steps (e.g. they both found the optimal solutions), the shorter program will win.

The program should return the solution as a sequence of blocks x-y coordinates (the coordinates of blocks to add to solve maze) in the format of your choosing :

11-3;15-6;19-12   

Meta

  • I cannot think of a simple algorithm that returns an optimal (best possible) solution in a reasonable time. I expect programs to use some heuristics to get non-optimal/near-optimal solutions. I made the grids 25 x 25 to make it challenging enough and prevent simple solutions like brute force.
  • Is this a duplicate? There is lot of related questions but I couldn't find anything related to block maze.
  • The tags are . Anything else?

EDIT : as AlienAtSystem pointed out in comments, there is an optimal algorithm for all cases. I made some tests: even a slightly modified Dijkstra's algorithm will work (it will find shortest path in a short time). I will not post this challenge as it is trivial. I leave it here in case someone else would have same idea.

\$\endgroup\$
  • \$\begingroup\$ By fewest total steps, do you mean cumulatively? \$\endgroup\$ – Corsaka Nov 20 '19 at 10:07
  • \$\begingroup\$ I mean the sum of all blocks. If solution for maze01 use 4 blocks and solution for maze02 use 5 blocks, it is 4+5 = 9 blocks in total. The lowest is the best. Someone who has 7+1=8 blocks will win. I have edited answer. \$\endgroup\$ – tigrou Nov 20 '19 at 10:37
  • \$\begingroup\$ You should allow people to have any output format as long as it has x first, y second. None of the mazes are duplicate. I can't think of any other tags. This should be good to post. \$\endgroup\$ – Corsaka Nov 20 '19 at 10:49
  • \$\begingroup\$ Should we add a test suite of some sort? Or how are you going to verify the score of a submission? But in general the challenge looks clear. A few questions: I assume there are some test cases among the 1000 requiring us to go right/up for the optimal solution, instead of only going left/down? Are the input-characters strict, or could we also use for example 012 for @.x respectively as integer-matrix? One other relevant tag: [path-finding] \$\endgroup\$ – Kevin Cruijssen Nov 20 '19 at 13:25
  • \$\begingroup\$ @KevinCruijssen I am planning to provide a program to validate solutions. right/up : some mazes might be shorter to solve that way but it is not allowed. The goal is go from top-left to bottom-right (not to cross from left to right). character set : programs should use the same characters as the test file. Anyway, using 012 might be a good idea (I might update the test file with such chars). There is no @ character in the test file since the start / end position are always the same. \$\endgroup\$ – tigrou Nov 20 '19 at 14:31
  • \$\begingroup\$ @tigrou Ah ok, so @ is not part of the input. In that case a binary-matrix with just 0s and 1s would be a suitable input format I guess. As for the right/up: I meant it for an input like this pastebin. With this maze you could walk from the top-left to bottom-right with just 2 x insertions (at the _ positions), but you'd have to travel up and left in the path from the top-left to bottom-right. But if I understand correctly we only travel right and down, so this would be the solution (with 4 insertions at _) instead? \$\endgroup\$ – Kevin Cruijssen Nov 20 '19 at 18:38
  • 1
    \$\begingroup\$ @KevinCruijssen : both solutions you posted are valid. You can go up / down / left right at any moment. \$\endgroup\$ – tigrou Nov 20 '19 at 18:42
  • \$\begingroup\$ I can think of an algorithm that should be optimal for all test cases. This could result in the tie-breaker problem if other people realize it, too. \$\endgroup\$ – AlienAtSystem Nov 22 '19 at 6:32
  • \$\begingroup\$ @AlienAtSystem : optimal algo : is it because of my test cases (which have some flaws) or the maze challenge in general ? \$\endgroup\$ – tigrou Nov 22 '19 at 8:20
  • 1
    \$\begingroup\$ @tigrou In general. It can be translated into a shortest path challenge over a considerably smaller graph. While A* wouldn't work on that one, other algorithms will. This wouldn't be short in terms of bytes, although I suspect not that much compared to other approaches, given that some part tasks need to be done by everyone. \$\endgroup\$ – AlienAtSystem Nov 22 '19 at 9:35
  • 2
    \$\begingroup\$ I think you don't need to give up entirely right away. While this doesn't work as test-battery challenge because it's too easy to get everything right, it should be good for posting as generic code golf. \$\endgroup\$ – AlienAtSystem Nov 22 '19 at 13:36
2
\$\begingroup\$

Times have changed!

(pun intended)


Preface

As mathematics progressed, mathematicians agreed upon the 'order of operations', to prevent mathematical expressions from becoming ambiguous.

Given the expression \$7 \times 6 + 5 \times 3\$ we know to first evalulate multiplication, giving \$ 42 + 15\$, which is equal to \$57\$.

But what if another group of mathematicians had agreed to evaluate addition before multiplication? This expression would become \$ 7 \times 11 \times 3\ = 231\$: which is different from our answer by an error of \$305\%\$!


The Challenge

Given a mathematical expression containing + (addition), * (multiplication), and the digits 0123456789, we can find:

  • \$E_1\$ - the 'real' value of the expression, when multiplication takes precendence.
  • \$E_2\$ - the 'alternate' value of the expression, when addition takes precedence.

Your task is to write a program or function which, given a string representing an expression, calculates and outputs the percentage error, \$\frac{|E_1 - E_2|}{E_1} \times 100\$.


Rules

  • WIP.
\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Chas Brown Dec 1 '19 at 22:33
  • \$\begingroup\$ @ChasBrown do you think it's similar enough to call this challenge a dupe? \$\endgroup\$ – FlipTack Dec 27 '19 at 14:14
2
\$\begingroup\$

Roll for Initiative!

Tags:

Introduction

In tabletop games like Dungeons and Dragons, when you begin a battle, all involved parties roll for initiative. In DnD 5e, this is 1d20 + DEX + Other bonuses, where DEX is the bonus given by your Dexterity stat. The characters that roll higher numbers go first. We'll use a similar, deterministic system in this challenge.

The Challenge

Write a program or function that, when given a list of characters, will output a list of characters in order of initiative.

A character is defined as this:

character = {
    name: "name" // a string
    statblock: [SPD, DEX, WHT] // a list of numbers
                               // DEX = dexterity, SPD = speed, WHT = weight
}

The formula for initiative is the following: $$\text{Initiative} = \left\lfloor{ \frac{\text{SPD}^2}{\sqrt{\lvert\text{DEX}\rvert}} }\right\rfloor - \text{WHT}$$

Input

A list of characters, unsorted. This can be a JSON object, a list of lists, a list of dictionaries, a series of strings etc.

It is guaranteed that all names will be unique.

Output

A list of characters, or character names, sorted by initiative order from highest to lowest, based on the above formula.

Rules

Sample IO

Input --> Output
[[Name, SPD, DEX, WHT], ...]
    --> [[Name, SPD, DEX, WHT], ...] (or [Name, Name, ...])
---------
[[Alice,1,2,3],[Bob,10,5,0],[Charlie,3,2,1]]
    --> [Bob, Charlie, Alice]
// Alice = -3, Bob = 44, Charlie = 5

[[Z,1,1,1],[B,1,1,1],[XY,5,1,1]]
    --> [XY, Z, B]
// Retain the order of characters from the input if they have the same initiative.
// Z = 0, B = 0, XY = 24

[[Neg,-3,-3,-1],[SomeNeg,5,-2,-4],[NoNeg,4,6,8]]
    --> [SomeNeg, Neg, NoNeg]
// Negative values are valid.
// Neg = 6, SomeNeg = 13, NoNeg = -2

[[Flo,1.5,2.5,3.5],[MoreFlo,2,2.5,3.5]]
    --> [[MoreFlo,2,2.5,3.5], [Flo,1.5,2.5,3.5]]
// Floats are also valid.
// Flo = -2.5, MoreFlo = -1.5

[[Lonely,1,2,3]]
    --> [[Lonely,1,2,3]]
// Input with 1 item.

[]
    --> []
// Empty input leads to empty output.
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use \left and \right in mathjax to make your brackets the right size. I also think that the output format is a little pointlessly strict - why not also allow just the list of names (same with requiring stable sorts)? \$\endgroup\$ – FryAmTheEggman Dec 4 '19 at 23:11
2
\$\begingroup\$

Score a 1 player game of Carcassonne

Carcassonne is a tile-based game, where the objective is to construct Roads, Cities and Monasteries, in order to score points. The game works by players taking turns to draw and place tiles to construct a landscape, then claiming roads, cities and monasteries. An example landscape is:

Example Landscape

There are \$19\$ distinct tiles (ignoring rotations), each of which contains at least one feature (Road, City or Monastery):

All tiles

Also, notice that the landscape must be consistent. This means that roads must connect to other roads, city edges must connect to other city edges and fields must connect to fields. Therefore, these tiles are inconsistent:

Inconsistent tiles

In a normal game of Carcassonne, each feature in the landscape is claimed by a player, and contributes to their final score. However, in this version, we will change the rules slightly (primarily for people who already know the standard Carcassonne rules):

  • There will only be \$1\$ player
  • The player will automatically own every feature in the landscape
  • There will be no "badge" score for cities
    • Notice that in some of the tiles in the pictures have badge symbols on them. In this challenge, we're ignoring them.

In a landscape, each feature is either complete or incomplete:

  • A complete monastery is one where it's tile is surrounded by \$8\$ tiles. This landscape contains one complete monastery (in the center) and one incomplete monastery (Top center).
  • A complete city is one fully enclosed by walls. This landscape has \$2\$ complete cities and \$2\$ incomplete cities.
  • A complete road is one where both ends terminate at either a city, village or by forming a loop. This landscape has \$2\$ complete roads and \$2\$ incomplete roads.

A landscape is scored as follows:

  • For every complete city, the player scores \$2\$ points for every tile containing that city. Therefore this city scores \$4\$ points, and this city scores \$18\$ points.
  • For every complete road, the player scores \$1\$ point for every tile containing that road. Therefore this road scores \$6\$ points, and this road scores \$2\$.
  • For every complete monastery, the player scores \$9\$ points, such as this monastery.

  • For every incomplete city, the player scores \$1\$ point for every tile containing that city. This landscape contains two incomplete cities, one scoring \$2\$ and the other 5.

  • For every incomplete road, the player scores \$1\$ point for each tile containing that road. This landscape contains three incomplete cities, scoring \$1\$, \$2\$ and \$3\$ points.
  • For every incomplete monastery, the player scores \$1\$ point for each tile that neighbours the monastery, plus \$1\$ for the monastery itself. This landscape contains \$3\$ monasteries, scoring 2, \$5\$ and \$7\$.

Take this landscape:

Example landscape 2

This landscape contains \$1\$ complete city, \$2\$ incomplete cities, \$4\$ complete roads, \$2\$ incomplete roads and \$1\$ incomplete monastery which scores \$4 + (3+3) + (3+2+6+2) + (4+2) + 4 = 33\$ points.


To avoid this challenge being about image processing, we can translate each tile into a list containing \$5\$ values, according to this legend:

[North edge, East edge, South edge, West Edge, # of cities]

0: Field
1: Road
2: City

For instance, this tile can be described as [2, 0, 1, 1, 1]. Using this legend, we can describe each tile uniquely, and it's rotations are rotations of the first four elements. The entire grid can be described as a rectangular matrix, with a \$20^\text{th}\$ distinct value for an empty square. Translating the first landscape into this format, we get:

[
 [             [],              [], [1, 1, 0, 0, 0], [1, 1, 2, 1, 1], [0, 1, 0, 1, 0],              [],              []],
 [[1, 0, 1, 0, 0],              [], [0, 0, 0, 0, 0], [2, 0, 2, 0, 2],              [], [0, 2, 2, 2, 1], [0, 0, 0, 2, 1]],
 [[1, 1, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 1], [2, 2, 0, 2, 1], [2, 0, 0, 2, 1],              []]
]

using [] to represent an empty square. The complete list of tiles (ignoring rotations) in the same grid as the second image is

[1, 0, 1, 0, 0] [0, 0, 1, 1, 0] [2, 1, 1, 1, 1] [0, 1, 1, 1, 0] [2, 0, 0, 0, 1]
[2, 2, 0, 2, 1] [0, 0, 0, 0, 0] [2, 2, 2, 2, 1] [2, 2, 0, 0, 1] [2, 1, 1, 2, 1]
[2, 2, 0, 0, 2] [0, 0, 1, 0, 0] [2, 0, 1, 1, 1] [2, 1, 1, 0, 1] [0, 2, 0, 2, 1]
[1, 1, 1, 1, 0] [2, 1, 0, 1, 1] [2, 2, 1, 2, 1] [2, 0, 2, 0, 2]

Your task is to take a matrix of lists in the above format representing a landscape and to output the score the player would have if they claimed all the features, complete or incomplete, in the landscape. You may take input in any convenient method, may choose any three consistent values to represent Field, City and Road edges and may use any value to represent the empty squares that isn't already a tile. Output must be an integer represented in your language's most natural format. If you aren't sure about an I/O format, just ask.

In addition, the inputs will always have consistent landscapes, and will always have at least 1 tile. Finally, the tiles will not be constrained by the tile availability (like in the real game).

This is so the shortest code in bytes wins.

Test cases

Test cases will be added in a bit


Meta

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

Posted

\$\endgroup\$
  • \$\begingroup\$ I don't think this is possible? Surely you can't tell what direction is involved with the mirrors, e.g. /1, can you tell if the pointer started on 1 going east vs / going north? \$\endgroup\$ – Jo King Dec 18 '19 at 9:10
  • \$\begingroup\$ @JoKing Hm yeah I think your right. I will try a little more but you are right that mirrors can't be used. \$\endgroup\$ – Post Rock Garf Hunter Dec 18 '19 at 15:06
  • \$\begingroup\$ @JoKing I actually do think this is possible. \$\endgroup\$ – Post Rock Garf Hunter Dec 18 '19 at 15:15
2
\$\begingroup\$

Traverse the Bridges of Köningsberg

The Seven Bridges of Köningsberg is a logical problem that singlehandedly kicked off both the fields of topology and graph theory. The city of Köningsberg was bisected by a river, with two islands in it. Thus the city spanned four landmasses. Connecting those were seven bridges. Leonhard Euler proved that it was impossible for a person to walk through Köningsberg and cross every bridge exactly once.

The bridges, increasingly abstract representation This is an increasingly abstract representation of the problem. The bridges can be represented as edges of a graph, and the landmasses as nodes. Try to start from one node, and "walk" to the other nodes, crossing every edge exactly once (crossing nodes multiple times is okay). Euler proved that it was impossible for Köningsberg. Info on how to solve this problem for any set of islands and bridges can be found on the Wiki page.

The problem

As input, your program/function should take an adjacency matrix, in any form that you wish (e.g. concatenating every number to a single string is fine, as is making a string list, or even a built-in matrix data structure if your language has one). The examples here are provided using a csv format.

The adjacency matrix for Köningsberg looks like this:

0;2;1;2
2;0;1;0
1;1;0;1
2;0;1;0

Each row and column represents the bridges from and to specific nodes. Node 1 (first row) has 2 bridges to node 2 (second column), and vice versa. Every bridge is bi-directional, so the matrix will always be symmetrical. Bridges from a node to itself are allowed (that does not make much sense architecturally, but topology nerds recently hacked several city planning agencies to make this challenge more interesting, so do not disappoint them) - but by convention such connections are counted double in the adjacency matrix.

Output, for any given adjacency matrix, a truthey/falsey value for whether it is possible to walk so that you traverse every edge exactly once. You don't need to end up back at your starting position - that's a different problem. The maximum amount of nodes/landmasses is 9, and the maximum amount of bridges between two landmasses is also 9. The maximum amount of bridges from one landmass to itself is 4 (notated as 8 in the matrix). There is no guarantee that all the landmasses are connected - if there's islands that you cannot reach, but you can reach all the bridges, then the answer is still truthey!

This is a challenge, so the shortest challenge in bytes wins!

Test cases

2

TRUE

2;8
8;2

TRUE

6;4;9
4;0;1
9;1;0

TRUE

6;2;4;0
2;4;3;9
4;3;2;3
0;9;3;4

TRUE

6;2;4;2;5
2;8;1;1;9
4;1;6;4;8
2;1;4;8;7
5;9;8;7;8

FALSE

0;0;0;0;0;0
0;0;0;0;0;0
0;0;0;0;0;0
0;0;0;0;0;0
0;0;0;0;0;0
0;0;0;0;0;0

TRUE (there's no bridges, so they can all be reached)

2;0;0;0;0;0;0
0;2;0;0;0;0;0
0;0;2;0;0;0;0
0;0;0;2;0;0;0
0;0;0;0;2;0;0
0;0;0;0;0;2;0
0;0;0;0;0;0;2

FALSE (every landmass only connects to itself)

0;0;0;0;0;0;0;0
0;0;0;0;0;0;0;0
0;0;0;0;0;0;0;0
0;0;0;0;0;0;0;0
0;0;0;0;0;1;0;0
0;0;0;0;1;0;1;0
0;0;0;0;0;1;0;1
0;0;0;0;0;0;1;0

TRUE (starting at a landmass with a bridge, you can reach all of them)

4;0;1;6;3;6;9;7;4
0;6;1;7;2;8;5;6;1
1;1;2;6;1;4;4;3;4
6;7;6;8;9;7;0;3;4
3;2;1;9;4;8;1;0;0
6;8;4;7;8;0;6;6;8
9;5;4;0;1;6;2;3;6
7;6;3;3;0;6;3;6;6
4;1;4;4;0;8;6;6;4

TRUE

Tags

Sandbox

Do I need to include the logical solution to the problem? It's pretty simple, but I might want to make figuring that out part of the challenge.

Any other feedback welcome, of course.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why are the outputs to 5th and 6th examples False? Looks like 5th is invalid (because it's not symmetric) and 6th should be True (because there are no bridges to start with, so we already walked over all bridges). \$\endgroup\$ – Bubbler Dec 17 '19 at 4:30
  • \$\begingroup\$ @Bubbler right on both counts (I was adjusting some of the squares but forgot the symmetry). Will update when I have time! \$\endgroup\$ – KeizerHarm Dec 17 '19 at 6:54
  • 1
    \$\begingroup\$ @Bubbler fixed! Thank you! \$\endgroup\$ – KeizerHarm Dec 17 '19 at 8:24
  • 1
    \$\begingroup\$ Pretty sure this is a duplicate \$\endgroup\$ – FlipTack Dec 20 '19 at 16:53
  • \$\begingroup\$ @FlipTack Oh, bugger. Is this one different enough because the input is an adjacency matrix rather than a list of bridges? \$\endgroup\$ – KeizerHarm Dec 20 '19 at 19:11
  • \$\begingroup\$ I wouldn't say so. Especially since the challenge isn't that interesting, just checking it's connected and there's 0-2 odd vertices. \$\endgroup\$ – FlipTack Dec 21 '19 at 6:55
  • \$\begingroup\$ Especially because the degree of a node is simply the sum over its line in the adjacency matrix. \$\endgroup\$ – AlienAtSystem Dec 22 '19 at 16:52
2
\$\begingroup\$

Decimal to String with Mandatory Length

Tags:

EDIT: NOTE: I still have to revise the rules, test cases, and reference implementation after realizing that 0.00000 wouldn't be the most accurate output of s="0.0000000001", n=7, which instead should be "100E-17" or "1.0E-15" or something similar.

Introduction:

Inspired by this SO question, which asks for the most accurate precision of decimal values using either rounding or scientific notation as string, with at most 15 characters long. This would include the -, ., and E in the output-string.

Challenge:

Inputs:

  • A decimal value as string \$s\$
  • An integer output-length \$n\$

Output:

  • A string of the most accurate representation of the given decimal value, with a length exactly equal to the output-length \$n\$. NOTE: the linked SO question ask for at most 15 characters long, but this challenge asks for exactly \$n\$ characters long instead.

Challenge rules:

  • The output-length input is guaranteed to be \$n\geq7\$
  • The decimal string input is guaranteed to be valid and non-empty
  • The output-string is guaranteed to only contain the characters 0123456789-.E (or e instead of E)
  • If the length of the integer part of a number (including - for negative values) is larger than the given output-length: use a scientific notation (with either e or E) and rounded precision. I.e. with inputs s = "-987654321987654321.987654321"; n = 15, the output is supposed to be "-9.876543220E17" (or "-9.876543220e17").
  • If the decimal value is an integer and the rule above doesn't apply, we add leading 0s and output without .0. I.e. with inputs s = "-123.00"; n = 15, the output is supposed to be "-00000000000123".
  • If the decimal value has an integer part of 0, it will be removed. Rounding or adding trailing 0s still applies when necessary. I.e. with inputs s = "-1.23"; n = 15, the output is supposed to be "-1.230000000000". With inputs s = "-0.123456789123456789"; n = 15, the output is supposed to be "-.1234567891235".
  • Rounding can be one of: HALF_UP, HALF_DOWN, HALF_EVEN (please specify which one your answer is using).
  • If multiple solutions are possible, just output one of them (i.e. s = "123.00"; n = 7 could be "0000123" or "01.23E2" or "1.230E2", and possible more variations as well.

General rules:

  • This is , so shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Test cases:

All these test cases will use the output-length as 15 (and rounding mode HALF_UP):

Input:                           Output:
"987654321987654321.987654321"   "9.8765432199E17"
"-987654321987654321.987654321"  "-9.876543220E17"
"1234567891234567.123456789"     "1.2345678912E15"
"-1234567891234567.123456789"    "-1.234567891E15"
"0.123456789123456789"           ".12345678912346"
"-0.123456789123456789"          "-.1234567891235"
"5.5555555555555555555555555"    "5.5555555555556"
"-5.5555555555555555555555555"   "-5.555555555556"
"123456789123456"                "123456789123456"
"-123456789123456"               "-1.234567891E14"
"123.00"                         "000000000000123" or "123000000000E-9"
"-123.00"                        "-00000000000123" or "-12300000000E-8"
"0.123"                          ".12300000000000"
"-0.123"                         "-.1230000000000"
"1.23"                           "1.2300000000000"
"-1.23"                          "-1.230000000000"
"0.000000000000001"              "10000000000E-25" // Currently incorrect in my reference implementation
"0"                              "000000000000000"

All these test cases will use the output-length as 7 (and rounding mode HALF_UP):

Input:                           Output:
"987654321987654321.987654321"   "9.88E17"
"-987654321987654321.987654321"  "-9.9E17"
"1234567891234567.123456789"     "1.23E15"
"-1234567891234567.123456789"    "-1.2E15"
"0.123456789123456789"           ".123457"
"-0.123456789123456789"          "-.12346"
"5.5555555555555555555555555"    "5.55556"
"-5.5555555555555555555555555"   "-5.5556"
"123456789123456"                "1.23E14"
"-123456789123456"               "-1.2E14"
"123.00"                         "0000123" or "01.23E2" or "1.230E2"
"-123.00"                        "-000123" or "-12.3E1"
"0.123"                          ".123000"
"-0.123"                         "-.12300"
"1.23"                           "1.23000"
"-1.23"                          "-1.2300"
"0.000000000000001"              "100E-17" or "1.0E-15" // Currently incorrect in my reference implementation
"0"                              "0000000"

Ungolfed reference implementation in Java. Created rather quickly to generate the test cases above, so if you see any errors or uncovered edge cases, let me know.

\$\endgroup\$
  • 1
    \$\begingroup\$ Suggest testcase: "0.0000000001", 10 -> ".000000000", "0", 10, "0000000000" \$\endgroup\$ – tsh Jan 13 at 1:50
  • \$\begingroup\$ @tsh Added (although I've used n=15 instead of 10 so I could add it to the other list instead of creating two separated test cases for the n=10. Principle remains the same for your test cases, so thanks for the suggestion! \$\endgroup\$ – Kevin Cruijssen Jan 13 at 7:44
  • \$\begingroup\$ @tsh Your test case actually made me realize that s="0.0000000001", n=10 should be "100000E-15" instead for the most accurate result. Will have to do some fixes to my reference implementation. \$\endgroup\$ – Kevin Cruijssen Jan 13 at 7:54
  • \$\begingroup\$ Why should it be 100E-17, not 1.0E-15? The rule makes me confusing. \$\endgroup\$ – tsh Jan 13 at 9:14
  • \$\begingroup\$ @tsh 1.0E-15 would be allowed as well. I still have to change the rules after realizing that 0.00000 would be an incorrect result for s="0.0000000001", n=7, but both 100E-17 and 1.0E-15 are allowed, since they are of length 7 and retain the same exact value as 0.0000000001. I currently don't have the time to revise the rules, test cases, and reference implementation unfortunately (and if I delete the Sandbox post temporarily I can't search back for it). \$\endgroup\$ – Kevin Cruijssen Jan 13 at 9:17
  • \$\begingroup\$ You say this challenge asks for exactly 15 characters long but you then have outputs of varying length. I assume you want the latter. I'm being pedantic, I know, but it's the only thing I can find to fix at the moment ;) \$\endgroup\$ – Lyxal Jan 13 at 9:28
  • \$\begingroup\$ @Jono2906 I've changed the part at the output-section. I hope it's a bit clearer now? \$\endgroup\$ – Kevin Cruijssen Jan 13 at 9:33
  • \$\begingroup\$ @KevinCruijssen it is clearer now. I mean, as I said, I was just being pedantic about things. \$\endgroup\$ – Lyxal Jan 13 at 9:34
  • \$\begingroup\$ @Jono2906 Well, it was still a valid remark that I agree with, so thanks. :) \$\endgroup\$ – Kevin Cruijssen Jan 13 at 9:36
  • \$\begingroup\$ Just another thing: Perhaps The decimal string input is guaranteed to be valid and non-empty should be The decimal string input is guaranteed to be a valid float and non-empty \$\endgroup\$ – Lyxal Jan 13 at 10:41
  • \$\begingroup\$ @Jono2906 Textual there isn't a difference between decimal/double/float, though. I had the sentence in my head as "the decimal string input is guaranteed to be (a) valid (decimal) and non-empty". I could change it to that if it makes it clearer, but talking about decimal first and float after that is more confusing than clarifying imho. But if you indeed meant "the decimal string input is guaranteed to be a valid decimal and non-empty" I'll change it. \$\endgroup\$ – Kevin Cruijssen Jan 13 at 11:49
  • \$\begingroup\$ @KevinCruijssen Yep, I indeed meant decimal. I've no clue why I said float. \$\endgroup\$ – Lyxal Jan 13 at 20:10
2
\$\begingroup\$

Internal Truth Machine

It's a normal truth machine but instead of taking input, it uses the first character of the program. Thus, internal.

Example: 0abcd prints 0 and halts, and 1abcd prints 1 infinitely.

New contributor
Want is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
1
\$\begingroup\$

.... . .-.. .-.. --- .-- --- .-. .-.. -..

Another Hello World challenge, this time with Morse code!

Taking no input, your program must output HELLO WORLD in audible Morse code, printing each letter as it is played. For the purpose of this challenge, the following Morse code guidelines will be followed:

Duration of sounds:

  • Dits are one time-unit long.
  • Dahs are three time-units long.
  • The gap between elements within the same character is equal to one dit.
  • The gap between characters within the same word is equal to one dah.
  • The gap between words is seven time units long.
  • The length of "one time unit" is up to the programmer, so long as it is consistent throughout the message.

Letters:

  • H: ....
  • E: .
  • L: .-..
  • O: ---
  • W: .--
  • R: .-.
  • D: -..


I'm a little iffy on that last bullet regarding duration. Should I set a hard standard, or a minimum? If so, what to?

\$\endgroup\$
  • 1
    \$\begingroup\$ Set a hard minimum for timing. Otherwise, a golfed solution might have 1 unit = 1 millisecond. \$\endgroup\$ – PhiNotPi Dec 16 '13 at 22:23
  • 6
    \$\begingroup\$ Tasks which take input are normally more interesting. \$\endgroup\$ – Peter Taylor Dec 17 '13 at 0:09
  • \$\begingroup\$ I guess that dahs need to be a continuous tone, not just two dits without a gap? \$\endgroup\$ – John Dvorak Dec 17 '13 at 6:32
  • \$\begingroup\$ @JanDvorak Correct. \$\endgroup\$ – Iszi Dec 17 '13 at 6:33
  • \$\begingroup\$ If you don't plan to post this, I would like to modify it and post it. (If you don't reply to this message within two weeks, by community standards, I am allowed to adopt the challenge.) \$\endgroup\$ – MD XF Dec 22 '17 at 2:41
  • \$\begingroup\$ @MDXF What do you suggest for modifications? \$\endgroup\$ – Iszi Jan 2 '18 at 15:18
1
\$\begingroup\$

How many pizzas do I need

Write a program that figures out the minimum number of pizzas I need to order and the amount of left overs I will have.

Requirements

  • Each pizza is 8 slices
  • Each person gets one choice of pizza topping, represented by a letter A-Z
  • Input in the format PVBC 2. Where each letter represents the choice of 1 person (e.g. P=Plain, V=Vegie, etc...), and the number is the amount of slices each person is allowed to eat. Letters can be in any order and do not need to be grouped.
  • If I don't need a full pizza I must be able to do half one topping and half another topping, the output for a half and half pizza will be denoted by X/Y where X and Y are different toppings
  • If I need multiple of a certain type of pizza they must be shown on one line (e.g. 2 x V Pizza). If there are different combinations the both result in the same, least, amount of pizzas, either output works
  • Output must match the format below of one type of pizza per line and a comma separated list of left overs. The output must show the minimum amount of pizzas and leftover possible.

Extra Credit

  • -20 - Take a 3rd argument that allows you to input the number of slices in a pizza, assume it will be an even number such that you can split it in half

Sample Input/Output

PCPVCB 3              (6 slices P, 3 slices V,  6 slices C, 3 slices B)
1 x P Pizza
1 x V/B Pizza
1 x C Pizza
2 slices P, 2 slices C, 1 slice V, 1 slice B left over

VBBCBBB 2             (10 slices B, 2 slices C, 2 slices V)
1 x C/V Pizza
2 x B Pizza
6 slices B, 2 slices C, 2 slices V left over

The 2nd example has many other combinations that could result in only 3 pizzas, this is just an example of what an output might be.

The shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ I can't say for sure, but I may have seen a similar challenge before. If not, it seems good to me. \$\endgroup\$ – user10766 Feb 18 '14 at 19:20
  • \$\begingroup\$ The use of the word "preferences" is confusing to me, because it suggests some kind of optimisation problem where people might get their second preference and you have to optimise for overall satisfaction. In addition, I don't find either the input or the output specification sufficiently clear. For the input, is there any guarantee that the letters are grouped (i.e. that PVP 1 will never be given as input)? And are the 4 letters given the only ones which may be used, or could there potentially be 26 different preferences? How much flexibility is there in the output? \$\endgroup\$ – Peter Taylor Feb 18 '14 at 21:12
  • \$\begingroup\$ @Danny, the one problem with this question is that because of my voracious appetite, there would be no left over pizza... ;) \$\endgroup\$ – WallyWest Feb 18 '14 at 21:15
  • \$\begingroup\$ @PeterTaylor I made edits to hopefully address all of the parts you saw that were possibly confusing. Can you look at the question again and let me know what you think. \$\endgroup\$ – Danny Feb 19 '14 at 13:44
  • \$\begingroup\$ @Danny You might want to add that you want the minimum amount of ordered pizzas/left overs - otherwise there exists a trivial solution where each person gets his own pizza (provided slices<=8). \$\endgroup\$ – Howard Feb 26 '14 at 8:19
  • \$\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 16:07
1
\$\begingroup\$

Resurrect Adobe SubScript.

In an obscure conference procedings volume of forgotton lore, there's a quaint little paper which describes an early effort to implement a published subset of Adobe Postscript. There a line in the bibliography! :) But it cannot be found Nobody's ever heard of it. :(

Adobe Systems, "SubScript Specification", 1984.

But there's obvious utility in such a thing. So this is a hypothetical Micro-Manual Postscript, and its name shall be ASS[*]. :)

ASS is a dynamically-typed stack-based programming language with powerful graphics primitives. It has support for floating-point arithmetic, arrays and dictionaries.

The scanner reads white-space delimited tokens and attempts to interpret the token as a decimal floating-point number with optional sign (+/-). The program may (but is not required to) support exponential notation. Failing to recognize a valid number, the token becomes a name object, an atomic symbol type which is identified by the name (an "interned" string).

Types

As suggested by the scanner behavior and the operator list , there are the following object types:

  • floating-point numbers (coerced to integer where appropriate)
  • names (usually an index into a string table, for easy comparisons)
  • arrays (an indexable sequence of objects)
  • dictionaries (a key-value map of objects)
  • operators (a pointer to a built-in function)

Operators

Operators are the basic actions predefined in the dynamic name space.

Stack Manipulation

  • any   pop   -
    pop an object from the operand stack

  • any1 any2   exch   any2 any1
    exchange top two elements

  • anyN anyN-1 ... any0 N   index   anyN anyN-1 ... any0 anyN
    retrieve object from stack by position

where N is treated as an integer.

Arrays.

  • N   array   array
    create a new array of length N

  • any0 any1 ... anyN-1 array   astore   array
    fill array with objects from stack

  • array   aload   any0 any1 ... anyN-1 array
    spill contents of array onto stack

  • [   any0 any1 ... anyN-1   ]   array
    construct an array

  • array index any   put   -
    put a value into array

  • array index   get   any
    retrieve value from array

where index is treated as an integer.

The typical way to implement the array syntax is using an auxiliary type, the marktype object, and an operator counttomark. This is an implementation detail and is not strictly required but may be found to be convenient.

  • -   [   mark
    produce marktype object as a sentinel on the stack

  • mark anyN anyN-1 ... any1   counttomark   mark anyN anyN-1 ... any1 N
    count objects up to mark

Then the ] operator may be implemented in terms of the other array operators.

  • mark anyN anyN-1 ... any1   ]   array
    { counttomark array astore exch pop }

Dictionaries.

  • N   dict   dict
    create a new dictionary, an associative container with room for N name-value pairs

  • dict   begin   -
    push dictionary on dictionary stack, making names part of the dynamic name space

  • -   currentdict   dict
    push copy of topmost dictionary on dictionary stack to the operand stack

  • -   end   -
    pop and discard the topmost dictionary on the dictionary stack

  • name any   def   -
    associate name with any value in topmost dictionary

  • name   load   any
    lookup name in each dictionary in the dictionary stack from the top-down, returning the first match, or error if not found

Matrices and transformations.

A matrix is a 6-number array [a b c d e f] which represent a left-multiplying affine transformation matrix with the constant right-most column omitted.

 a b 0
 c d 0  =>  [a b c d e f]
 e f 1
  • -   matrix   matrix
    returns a new identity matrix [1 0 0 1 0 0]

  • matrix   setmatrix   -
    make matrix the current transform in the graphics state

  • -   currentmatrix   matrix
    return current transform from the graphics state

  • x y   transform   x′ y′
    transform (x,y) pair by current transformation matrix

Transforming a point involves multiplying the homogeneous vector through the transformation matrix:

          [a b 0]
[x y 1] * [c d 0] => [x' y' 1]
          [e f 1]

or, equivalently

x' = a*x + c*y + e
y' = b*x + d*y + f

Path description.

  • -   newpath   -
  • x y   moveto   -
  • x y   lineto   -
  • -   closepath   -

Clipping.

  • -   clip   -
  • -   clippath   -

Painting.

  • -   erasepage   -
  • -   fill   -
  • -   showpage   -

The fill operator is where the magic happens. This operator is responsible for performing all of the graphics algorithms in sequence:

  • Shape Mapping
    Tranform the coordinates of the path from user space to device space using the current transformation matrix.

  • Shape Clipping
    Clip the portions of the path that lie outside the clipping path.

  • Filling
    *Perform a scan-line rasterization of the (may assumed closed-) polygon described by the path into the output frame buffer.

And showpage copies the contents of the framebuffer to the actual output mechanism (window or file as described above).

... need to fill this out a little more. Math, graphics state, errors. Describing stroked lines is too much, I think. I'm not sure if it needs the forall operators for iterating through arrays and dicts. I'd like to avoid any need for overloading different types under the same operator name, and calling back to user code from an operator.

Output may be to a window, or to a file in a simple format, like pgm or even a text-file of hashes and spaces for rough bitmaps. No half-toning. Only bi-level filling of convex polygons will be required. But a program may handle more colors if desired.

This is CW in case anybody wants to help me type-in the basic operators.

Questions

Does it need anything more? Should something be removed as unnecessary? Does anyone have the spec??

Perusing my ps implementations of the graphics portions linked in the comments, I've noticed the following needed operators:

length
sub
roll
add
eq
array copy
mul
div
ne

I think it needs loops, too. It's possible to do with just recursion, of course, but loops are nice. And length, I think, needs to be polymorphic, operating on array or dict to retrieve the size for making copies and calculating indices. Add sin and cos, too.


And this would be a .

[*] The moniker "ASS" is not intended as a disparagement of Adobe Systems nor any of their stupendous intellectual property. Rather it is merely intended to express frustration at the encountered difficulty in locating this document.

\$\endgroup\$
  • \$\begingroup\$ So this is intended to be a subset of PostScript: are you going to point people at a PS spec for the nitty-gritty details about things like the precise implementation of path filling? Also, if the idea is to be minimalistic, why have both mark and [? \$\endgroup\$ – Peter Taylor Jan 11 '14 at 13:19
  • \$\begingroup\$ I'm hoping I can concisely specify everything so it's self-contained and not need to refer to a PS spec. ... Good point about mark. I suppose I can require [ and ] and suggest mark ... counttomark as a possible way to implement it. \$\endgroup\$ – luser droog Jan 11 '14 at 13:22
  • \$\begingroup\$ oh. I see what you mean now. removed mark as a separate entity. It isn't needed. \$\endgroup\$ – luser droog Jan 11 '14 at 13:32
  • \$\begingroup\$ My idea is to follow the most basic part of the original Warnock paper which is the basis of the Adobe Image Model. I've got some excerpts here. \$\endgroup\$ – luser droog Jan 11 '14 at 13:46
  • \$\begingroup\$ I don't see any way to create a non-identity matrix. \$\endgroup\$ – Peter Taylor Jan 24 '14 at 9:20
  • \$\begingroup\$ You can construct any matrix using the array notation. There should also be user space transforms: rotate, scale and translate. They're usually part of the graphics state, so I didn't put them under matrices. \$\endgroup\$ – luser droog Jan 24 '14 at 9:25
  • \$\begingroup\$ This spec from the 80s would be gold for implementing postscript. Offering a glimpse at the intermediate stage between the Warnock/Wyatt paper (which describes the image model in the syntax of the Xerox Mesa language) and the PLRM 1ed. Warnock/Wyatt has been described as "smuggling" the ideas out of Xerox. ... Ugh. I forgot to add some control structures. \$\endgroup\$ – luser droog Mar 1 '14 at 10:22
  • \$\begingroup\$ I've got implementations of paths, matrices, clipping, and filling in postscript. Perhaps I should wrap these up and just require the data structures and scanning to load and use them. \$\endgroup\$ – luser droog Mar 1 '14 at 11:33
  • \$\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 16:08
  • \$\begingroup\$ Thanks! ... Done. \$\endgroup\$ – luser droog Jun 11 '17 at 10:00
1
\$\begingroup\$

Convert input to ASCII Semaphore

With monitor resolutions getting higher and font sizes getting lower, a good programmer has to make efforts to ensure that output is accessible to the visually impaired. This can be problematic when the only display is in text. Toward this end, your assignment (if you choose to accept it) is to write a program that converts text input into ASCII art flag semaphore.

Input

  1. Your program must accept any letter in the ASCII character set from A to Z (case insensitive) and spaces.
  2. The program can accept input in any way that is convenient for the language it is written in (stdin, command line, file, etc.).

Output

  1. The program should output an ASCII art representation of the input string in flag semaphore. Follow this link to see the expected encoding.
  2. Line feeds and carriage returns should be interpreted as spaces.
  3. Numbers and other non-letters in the input may be ignored.
  4. You may use whatever ASCII art representation of the semaphore sender you like, but it must contain a person holding two flags and have distinct arms, legs, head, and flags. It must be at least 10x10 characters.
  5. Output may be either horizontal or vertical.

Example

Input: Hello

Output:

           ###
           ###
            #
 _____########
|  |       ###
|__|      ####
         # ###
        #  ###
       /   # #
      /\   # #
     /  \  # #
     \  /  # #
      \/  ## ##
                    /\
                   /  \
                  /\  /
                 #  \/
           ###  #
           ### #
            # #
          ####
         # ###
         # ###
         # ###
         # ###
         | # #
         |__ #
         |  |#
         |__|#
          ## ##
                    /\
                   /  \
                  /\  /
                 #  \/
           ###  #
           ### #
            # #
           ###
          ####
         # ###
        #  ###
       #   ###
      /    # #
     /\    # #
    /  \   # #
    \  /   # #
     \/   ## ##
                    /\
                   /  \
                  /\  /
                 #  \/
           ###  #
           ### #
            # #
           ###
          ####
         # ###
        #  ###
       #   ###
      /    # #
     /\    # #
    /  \   # #
    \  /   # #
     \/   ## ##
   /\
  /  \
  \  /\
   \/  #
        #  ###
         # ###
          # #
 _____########
|  |       ###
|__|       ###
           ###
           ###
           # #
           # #
           # #
           # #
          ## ##

Scoring

This is code golf. Shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ define "easily recognisable". Would a simple 3x3 compass (say, with a head if not covered) do? say:.o. -|. /|. ; or even: ... xx. x.. (read by lines, dots represent spaces) \$\endgroup\$ – John Dvorak Mar 6 '14 at 20:16
  • \$\begingroup\$ @JanDvorak Good catch. Edited to include distinct items that must be present and a minimum size. I'm not exactly sure how to make that rule more clear. \$\endgroup\$ – Comintern Mar 6 '14 at 20:34
  • \$\begingroup\$ Define "person holding two flags". Is what I drew a person? Is this a (lying, due to formatting issues) person: o--? Are three x's on a vertical line a person? \$\endgroup\$ – John Dvorak Mar 6 '14 at 20:43
  • \$\begingroup\$ @JanDvorak Ack! had to many tabs open and forgot to save my edit. I think number 4 for output should cover that. \$\endgroup\$ – Comintern Mar 6 '14 at 20:47
  • \$\begingroup\$ Define "distinct arms, legs, head, and flags." But I suggest allowing very small figures as well, otherwise this will turn into a kolmogorov-complexity-like question with very little of the code actually involving generating a pair of directions. \$\endgroup\$ – John Dvorak Mar 6 '14 at 20:51
  • 2
    \$\begingroup\$ Very similar to this question. The ascii art is more complex here so perhaps it's not close enough to be called a duplicate... \$\endgroup\$ – Gareth Mar 6 '14 at 22:20
  • 2
    \$\begingroup\$ I disagree with @JanDvorak: I think this would be better with a fixed output spec which must be followed exactly. That way people can golf their code rather than the output. \$\endgroup\$ – Peter Taylor Mar 6 '14 at 23:59
  • \$\begingroup\$ Standard figures seem best to me as well. If you demonstrate a full "clock" of hand positions for the standard figure, then you can require those as output. That's easier to assess than free reign for variations. \$\endgroup\$ – Jonathan Van Matre Mar 7 '14 at 0:14
1
\$\begingroup\$

Weighted letters combination to get 2014.

If a=1, b=2, c=3, d=4,...z=26, which letter combinations (in particular order) when operated by any one or two or three or all four of +,-,X,/ (in any order) will give 2014 as the result?

For example, j*t*j+n=10*20*10+14=2014, t*j*j+n=20*10*10+14=2014 and n+j*t*n=14+10*20*10=2014

are three different combinations.

N.B. - max number of consecutive same letters should be 2, see link http://www.oxforddictionaries.com/words/are-there-any-english-words-containing-the-same-letter-three-times-in-a-row

\$\endgroup\$
  • 1
    \$\begingroup\$ This needs a lot of work. Firstly, questions which don't take input are almost always improved by generalising them to take a parameter: in this case, 2014 could be the test case rather than a hard-coded constant. You haven't specified what the output should be: do you want a list of all solutions (which could be an insanely large list, even if equivalence classes under permutation of arguments are represented by a single element)? Asking for any solution has a trivial approach of just building a long sum. \$\endgroup\$ – Peter Taylor Mar 9 '14 at 8:27
  • 1
    \$\begingroup\$ Then there's the issue of your final constraint and link: it appears to have no relevance at all to the question, unless you previously intended to state that the expression should, once all operators are removed, form an English word. In that case, it would be as well to just provide a link to a dictionary file for Windows users. You should also be aware that your question might be closed as a near-duplicate of one of these earlier questions. \$\endgroup\$ – Peter Taylor Mar 9 '14 at 8:32
  • \$\begingroup\$ @PeterTaylor, thanx for pointing out the difficulties, I was just playing with this idea, if we choose the word "mathematics", it has 10 places for +,-,* and /, each of the 10 places can have any one of the four operators, that amounts to $4^{10}=1048576$, that's just impractical to find out what just one word "mathematics" adds up to. \$\endgroup\$ – Vikram Mar 10 '14 at 11:59
1
\$\begingroup\$

Your task, should you choose to accept it, is to convert an image into ASCII art. Essentially, your program has to do precisely what picascii.com does.

Rules:

  • You must take the image from stdin or read it from a file specified in the command line.
  • You must output to stdout or to a filename specified in the command line.
  • Your program must take input in a format that ImageMagick supports. You can choose any format you want, however. If you want to read ppm images and we have to pass a jpeg through ImageMagick first to use your program, that's fine.
  • Given the above, your program itself must use only standard libraries, even for loading the image.
  • You must only output printable ASCII characters (that's 32-126 plus CR and LF).
  • You can choose in which font or setting your image should be viewed in, e.g. it might look good in a terminal but awful in a stackexchange code block, or vice versa, or maybe it only looks good with Courier New size 12, etc.
  • The largest edge of your output must be at least 25 characters and at most 200 characters long.
  • Aspect ratio must be preserved as much as possible within one fixed-width character size. e.g. if you have a 400x320 pixel image, and the fixed-width font you're outputting for is 8x13 including spacing, your output must be at least 25x12 characters, or it can be 50x25, 125x62, etc., with a maximum size of 200x98.
  • Provide at least two sample inputs & outputs with your submission. Outputs can be stackexchange code blocks or links to paste bins or screenshots of the output viewed in the environment you intended it for, etc.
  • Your score is the byte count of your source code. Lowest score wins.

However, I want the output to bear some reasonable resemblance to the input. I don't want this to be subjective. I'd rather have a hard limit that people can hack around.

Opening suggestion: maybe something like: given a font size of 8x13, if the image is converted to grayscale and quantized to 8x13 blocks, and your solution is converted to an image, scaled to fit, and also quantized to homogeneous 8x13 blocks where the value of each block is the percentage of filled-in pixels for each block, the average distance between the image blocks and your output blocks must be less than X.

\$\endgroup\$
  • \$\begingroup\$ You should delete it from the main site for now because you can't really change the rules once somebody posts an answer. You can repost it when you think it is ready. \$\endgroup\$ – user10766 Mar 11 '14 at 18:53
  • \$\begingroup\$ @hosch250: Good idea, just deleted it. gotta make it a good one! \$\endgroup\$ – Claudiu Mar 11 '14 at 19:02
  • \$\begingroup\$ @hosch250: The link isn't broken, it's just a deleted question, and can only be viewed by me and the mods. I wanted to not lose the link but it's there in the edit history I guess. \$\endgroup\$ – Claudiu Mar 11 '14 at 20:26
  • \$\begingroup\$ It is still in your account page too. \$\endgroup\$ – user10766 Mar 11 '14 at 21:55
  • \$\begingroup\$ I think this would be quite dull as a code-golf challenge. The optimal solution is to simply read every other line of a PGM file and convert each number into ASCII 32 (space) or 33 ('!') based on some threshold value. Without a code length restriction, we could add more interesting features like Floyd-Steinberg dithering and matching letter shapes to image features (e.g., using / and \ in places where diagonal likes are detected). \$\endgroup\$ – squeamish ossifrage Mar 14 '14 at 0:15
  • \$\begingroup\$ @squeamishossifrage: Hmm interesting. I was going for making an objective criterion that would make that not the optimal solution, so you'd have to use more than a few characters, but that'd be awkward. Making it a popularity contest would definitely lead to more creative solutions.. I will consider it \$\endgroup\$ – Claudiu Mar 14 '14 at 0:53
  • \$\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.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:19
1
\$\begingroup\$

music theory challenge

Create a program that takes some input in the form of frequency, waveform, and duration that generates an audio stream based on the input.

You can take input parameters however you choose, but if I input (translated to your method) 440Hz, sin(x), 3 seconds, your program should play or create a file for a sound 3 seconds long at 440 hertz on a sine wave.

Also, any output should be musically correct as far as frequency is concerned. See http://www.phy.mtu.edu/~suits/notefreqs.html for example frequencies

Since this is a popularity contest, the rest is up to you. I bid you Good programming!

Oh, and any use of external functions or APIs is ok, as long as they weren't developed specifically for this contest.

\$\endgroup\$
  • \$\begingroup\$ If the program takes "input in the form of frequency, waveform and duration" then where do linear functions fit? What do you mean "output should be musically correct as far as frequency is concerned" given that the input is frequency? Is it supposed to correct the input: "You said 494Hz but you must mean 493.88Hz"? And simple synth has been done before in various guises: see music. To differentiate this and make it non-trivial you could perhaps specify a set of basic synth operations which need to be configurable (e.g. input specifies generators, envelopes, filters, mixers). \$\endgroup\$ – Peter Taylor Mar 14 '14 at 8:39
  • \$\begingroup\$ On second thoughts, that would probably work better as a Code Review Code Challenge \$\endgroup\$ – Peter Taylor Mar 14 '14 at 9:23
  • \$\begingroup\$ @PeterTaylor I didn't even know about Code Review Code Challenges <intrigued>. Linear isn't the right word...and I think that statement is redundant anyway, so I'll nix it. \$\endgroup\$ – David Wilkins Mar 14 '14 at 12:44
  • \$\begingroup\$ Actually, I'm going to re-write this challenge...I don't know yet whether it'll be here of on CR \$\endgroup\$ – David Wilkins Mar 14 '14 at 13:07
1
\$\begingroup\$

Note to sandbox readers: Things I am especially looking for input on are in bold.

David and Goliath

You are David, fighting Goliath in a turn based game. Can you kill Goliath?

  • Goliath is big. He is a 3x3 monster, and fast... but not very maneuverable.
  • David is maneuverable, but not very fast. He does have a slingshot, though.

Goliath's turn

  • Goliath may only move in a straight line, up, down, left, right, or 45 degree diagonal (e.g. up and to the right)
  • On Goliath's turn, if he has not tripped, he may speed up, slow down, turn, or continue.
    • Continue: Goliath goes in the same direction at the same rate.
    • Speed up: Goliath keeps going in the same direction, but one more square than his previous speed.
    • Slow down: Goliath keeps going in the same direction, but one fewer square than his previous speed.
    • Turn: As slow down, except Goliath also turns 45 degrees.
  • Speed zero exception: there is no such thing as speed zero. If Goliath moved at speed 1 in any direction last turn, he may move at speed 1 in any other direction he chooses.
  • If Goliath has tripped, it takes him 1 turn to stand up. Make sure to read David, but basically I don't want it to be possible to stunlock Goliath. This needs work, suggestions appreciated
  • Goliath is greedy. He will move whatever move gets his center square to be the shortest distance in total squares from David. Ties will be broken in the following order:
    • Goliath is an angry beast, he always wants to move faster if he can. He will move at the fastest possible speed. Note: this is only used to break ties. If his speed is 4 and he is exactly 3 squares away from David, he will move 3 squares.
    • Goliath prefers not to turn.

David's turn

This is where your ingenuity comes in. It is your job to program a David algorithm (Is this too much? Would a user interface be a better question?) to defeat Goliath.

Here are David's movement rules:

  • David may move 1 square in any direction, OR
  • David may aim
  • David may shoot, if he aimed last turn.

Other details

  • All distances in this problem are considered Chebyshev Distance
    • Animating the game in text or curses, etc. should look similar to a roguelike.
  • Bullets move effectively instantaneously. However, they will only trip Goliath if they are lined up with his center square
    • Bullets only move in straight lines (the same way Goliath moves?) Is this best?
  • Every time you shoot Goliath, he takes one damage.
  • It takes 3 bullets to kill Goliath. (Or more? or less?)
  • Goliath will kill David if any part of him overlaps with David's square.

The game board

David and Goliath are fighting on the surface of a Torus (i.e. a flat map that wraps east-west and north-south). Goliath CAN see over the edge of the game board.

Your job:

Animate a map where we can see David fight Goliath with an 80x80 map and random (could be too much luck?) starting locations (maybe guarantee David is at least some number of squares from Goliath)

Scoring:

Not sure here:

  • Most kills in 10000 turns?
  • Fastest kill?
  • Golf of a program that animates and shows a combat between David and Goliath where David wins?

Other concerns:

  • I'm concerned David is too slow. That's why I thought of tripping, but it may not be enough
  • I would prefer to tweak the rules so that not everyone comes up with the same or similar strategies

ALL input is appreciated, from minor changes to big ones.

\$\endgroup\$
  • \$\begingroup\$ @githubphagocyte I want Goliath's behavior to be mostly deterministic (only if there are no tiebreakers left), the creativity in this problem should be in how you choose to program David. \$\endgroup\$ – durron597 Apr 10 '14 at 20:01
  • \$\begingroup\$ Does Goliath have a top speed? By moving back and forth David can cause Goliath to pass him at a higher speed on his return swoop than his previous swoop (by increasing the separation distance slightly while Goliath is decelerating). This allows David to accelerate Goliath to arbitrary speeds. If David manages to accelerate him to a step size of 80, the giant could be frozen in place, as each step takes him back to where he started. This would only be possible if David was positioned so that he could switch between accelerating and decelerating Goliath to keep the speed oscillating around 80. \$\endgroup\$ – trichoplax Apr 10 '14 at 20:16
  • \$\begingroup\$ On the problem of tiebreakers with Goliath's behaviour being deterministic: If the initial positions are chosen randomly each time, then simply running a few more games per tied winner should break the tie for any player that cannot consistently reach 100%. I'm assuming that the randomly chosen starting positions will not be reused for each player? \$\endgroup\$ – trichoplax Apr 10 '14 at 20:20
  • \$\begingroup\$ Since this is mostly deterministic, someone may program a player that has 100% success. Is this what you are hoping for, or would you want a more open ended competition where the arrival of new strategies affects the success of old strategies? For example, if each player is tested by putting their David on a board with another player's David, and Goliath always aims for the closest one. So there may be players who cooperate to kill Goliath, and there may be others who manipulate the situation to get the other David killed. This would avoid everyone converging on the same optimum solution. \$\endgroup\$ – trichoplax Apr 10 '14 at 20:25
  • \$\begingroup\$ Goliath does not have a top speed, but Goliath wants to STOP on David's square. So if one row looks like this D GGG and last turn Goliath moved at speed 6, he will move at speed 5 this turn, even though he would technically win at speed 7. \$\endgroup\$ – durron597 Apr 10 '14 at 20:38
  • \$\begingroup\$ @githubphagocyte Your idea about multiple Davids with Goliath going for the closest David is a good one. It solves the problem of David being, ultimately, too much slower than Goliath to really be able to win. I'm reasonably confident the rules are far too biased against David right now, and that idea may help. \$\endgroup\$ – durron597 Apr 10 '14 at 20:40
  • \$\begingroup\$ I understand the rough idea of Goliath aiming to decelerate to zero by the time he reaches David's position. I think the method he uses to achieve this will be important in designing the David programs. Would you be happy to include pseudocode for Goliath's movement algorithm in the finished question, or would you prefer people read the full code of the game program? \$\endgroup\$ – trichoplax Apr 10 '14 at 22:20
  • \$\begingroup\$ Is there a preferred language? Or a defined interface open to any language? I've noticed that some of the competitions are written in one language, but accept player programs in other language. Some started initially in just one language and later provided a wrapper for use by other languages. \$\endgroup\$ – trichoplax Apr 10 '14 at 22:24
  • 1
    \$\begingroup\$ I'm not convinced that David is necessarily at such a disadvantage. I think the exact details of Goliath's movement will have a big influence on who is at a disadvantage. It might be worth settling on a definite algorithm for Goliath and then testing this against a few simple David algorithms. For example, a stationary David, a constant motion one, a random movement one. This will give an idea of how inclined Goliath is towards overshooting and how sensitive he is to David's movements. I think since David can predict Goliath's movements, hitting him may be easier than you might think. \$\endgroup\$ – trichoplax Apr 10 '14 at 22:35
  • \$\begingroup\$ If you want to see lots of competing strategies then my recommendation would be to make this a king of the hill competition rather than a golf contest. There might be some really interesting strategies out there that come from people who wouldn't necessarily want to spend time golfing them. I'd rather see all the strategies, from the golfers and non golfers... \$\endgroup\$ – trichoplax Apr 10 '14 at 22:41
  • \$\begingroup\$ Avoiding stunlock: David or Goliath could be moved to a different location when Goliath is tripped, so that Goliath is no longer in the right position to be shot at without David moving first (assuming the shots are only permitted when Goliath is in one of the 8 compass directions). David could have a waiting period to reload before he can fire again. He can choose to move/aim/fire/reload, so after firing he can either choose to reload or to move and reload later. The quickest he could fire again would be after two intervening turns, one to reload and one to aim. \$\endgroup\$ – trichoplax Apr 10 '14 at 22:54
  • \$\begingroup\$ @githubphagocyte lots of great stuff here but I'm traveling this week so my response time will likely be slow. I don't like the idea of requiring a language though. I'll keep thinking about it, keep up the great ideas! \$\endgroup\$ – durron597 Apr 11 '14 at 15:31
  • \$\begingroup\$ Thanks for letting me know. No rush since it's still in sandbox - take as long as it needs to get it ready... \$\endgroup\$ – trichoplax Apr 11 '14 at 19:54
1
\$\begingroup\$

Divisibility testing

This question is related to another StackExchange question:

enter image description here

Your task

Write a program that tries to find such an n. This question is a challenge.

Format of your answer

Your answer should include

  • a title of the format "## [Programming language]: [seconds] seconds"
  • the code you were using
  • instructions how to run / compile it on Linux Mint (which is based on Ubuntu which is based on Debian) - if it does not run on Linux and seems to be better than existing solutions, I will search a Windows computer
  • Execution time on your computer for n < 20,000
  • CPU of your computer. If it's an Intel CPU: please link to ark.intel.com. You can find your CPU with cat /proc/cpuinfo.

What could be done

The following Python code needs 229.21s seconds to execute on my machine:

#!/usr/bin/env python


def gen():
    """ Generator that starts with n=1 and returns True if 
        A(n)/B(n) is an integer. Otherwise, it returns False.
    """
    num = 0
    den = 0
    k = 1
    while True:
        num += k**k
        den += k
        yield num % den == 0
        k += 1

if __name__ == "__main__":
    n = 1
    for number in gen():
        if number:
            print("n = %i works!" % n)
            if n > 1:
                break
        if n == 30000:
            print("No solution found.")
            break
        n += 1

Things that could probably improved are:

  • Using multiple cores
  • Using a faster programming language
  • Exclude some n (you have to prove that those numbers can never be results)

Note: When you find some n that can be excluded, you get a time bonus. The number of seconds you get as a time bonus is the number of seconds that it speeds up my Python implementation from above.

  • Prove that there cannot be any n > 1 so that A(n)/B(n) is an integer. You will win if you find that. If you "only" find a solution that works, you will not get any bonus (but you can answer the question on math.SE :-) )
  • Find a faster way to calculate the hyperfactorial A(n).

Testing system

I have an Intel P6200 CPU (2.13 GHz, 2 cores, 3 MB cache). I will run your code on my system to make it comparable. I will take the time this way:

time python testit.py

Tags I will use:

(This will not be part of the question, of course.)

\$\endgroup\$
  • 1
    \$\begingroup\$ A(n) is not actually the hyperfactorial - it's a kind of related summand, but the hyperfactorial is the product of those terms. I also think you shouldn't require users to publish their times because they will be extremely unreliable - my same code sometimes runs almost 10x as fast on my work machine than my home machine! \$\endgroup\$ – alexander-brett Apr 20 '14 at 20:42
  • \$\begingroup\$ Why ask people how fast code ran on their machine? Different computers run at different speeds. \$\endgroup\$ – golfer9338 Apr 24 '14 at 11:09
  • \$\begingroup\$ Can I take ownership of this question and post a completed question on the main site. Let me know in 1 week \$\endgroup\$ – george Dec 2 '16 at 23:07
  • \$\begingroup\$ @george Sure. Please let a link here so that I can have a look at the question. \$\endgroup\$ – Martin Thoma Dec 2 '16 at 23:25
1
\$\begingroup\$

Generate a text-art table

Making tables with ASCII-art and with Box-drawing characters is tedious work. Let's simplify this work by automating it with a program:

Input and Output:

The first line of input signify's whether the user wants an ASCII table or a Box-drawn one. This is simply given as a number: 1 for ASCII, 0 for Box-drawing.

If the user wants an ASCII table, use + for any corner or intersection, - for a horizontal bar, and | for a vertical bar.

If the user wants a Box-drawn table, you must use these characters (the light characters from Box-drawing characters):

┌
└
┐
┘
├
┬
┴
┤
─
│
┼

The next lines of input will be tab delimited, newline delimited entries. Newlines delimit rows of the entry, and tabs delimit columns. If the user wants multiple columns on a cell, this will be delimited by a \. \\ asks for a literal \. If the user wants to join two cells, this will be indicated by \=.

You will output a table that meets the user-defined specifications. Space-buffer the cell content, that is, prepend and append a space when inserting it in the table. When centering the text, prefer prepending spaces to appending them. Shrink the leftmost cell possible when there is a choice. Columns always line up, whether the lines form from a \ or a tab.

For example, this input ( is a tab):

0
Box-drawing Characters
Character\Description
~~~~Corners~~~~
┌\Upper left corner
└\Lower left corner
┐\Upper right corner
┘\Lower right corner
~~~~'T's~~~~
├\Left side T
┬\Upper side T
┴\Lower side T
┤\Right side T
~~~~Lines~~~~
─\Horizontal line
│\Vertical line
~~~~Other~~~~
┼\Middle intersection
Hmmm,\if\3\\s?
This\Is\The\End

Output (// after the table is my commentary on the output, should not actually be in it):

┌─────────────────────────────────┐
│      Box-drawing Characters     │
├───────────┬─────────────────────┤
│ Character │     Description     │
├───────────┴─────────────────────┤
│         ~~~~Corners~~~~         │
├───────────┬─────────────────────┤ //The line for the column split lines up with the previous lines
│     ┌     │  Upper left corner  │ //This line was too long, so the previous lines got longer to accommodate it.
├───────────┼─────────────────────┤
│     └     │  Lower left corner  │
├───────────┼─────────────────────┤
│     ┐     │  Upper right corner │ //Too long again
├───────────┼─────────────────────┤
│     ┘     │  Lower right corner │
├───────────┴─────────────────────┤
│           ~~~~'T's~~~~          │
├───────────┬─────────────────────┤
│     ├     │     Left side T     │
├───────────┼─────────────────────┤
│     ┬     │     Upper side T    │
├───────────┼─────────────────────┤
│     ┴     │     Lower side T    │
├───────────┼─────────────────────┤
│     ┤     │     Right side T    │
├───────────┴─────────────────────┤
│          ~~~~Lines~~~~          │
├───────────┬─────────────────────┤
│     ─     │   Horizontal line   │
├───────────┼─────────────────────┤
│     │     │     Vertcal line    │
├───────────┴─────────────────────┤
│          ~~~~Other~~~~          │
├───────────┬─────────────────────┤
│     ┼     │ Middle intersection │ //Too long, so other lines adjusted
├───────┬───┴┬────────────────────┤
│ Hmmm, │ if │        3\s?        │ //Because the user wants to divide into 3, the cells don't line up with the previous ones.
├──────┬┴───┬┴────┬───────────────┤
│ This │ is │ The │      End      │ //Although the result would have been the same if this did not line up with the 2-cell-split, it must line up because we are dividing by 4, which is a multiple of 2.
└──────┴────┴─────┴───────────────┘

This input:

1
hello→World→!
\Lorem→Ipsum.\Quick→Fox
\=\=
This is\ → the\ last→row.\

Produces this as an output:

+------------------+----------------+---------+
|       hello      |      World     |    !    |
+---------+--------+--------+-------+---------+
|         |  Lorem | Ipsum. | Quick |   Fox   |
+---------+--------+--------+-------+---------+
|                                             |
+---------+--------+--------+-------+------+--+
| This is |        |   the  |  last | row. |  |
+---------+--------+--------+-------+------+--+


Meta:

Is my specification well defined enough yet?

\$\endgroup\$
  • 4
    \$\begingroup\$ I don't think I understand the layouting rules. Please provide more examples or some pseudocode. Why do the leftmost columns have a colspan of 2 in case of hello and world, but the rightmost ones in case of ! and Fox? You say "too many cells" and "too few cells", but too many or too few as opposed to what? \$\endgroup\$ – John Dvorak May 5 '14 at 5:51
  • \$\begingroup\$ I think this would actually be most interesting if you accepted input in basic html format. It would be like writing an ASCII html table renderer. I think that would be super interesting \$\endgroup\$ – Cruncher May 9 '14 at 12:55
  • \$\begingroup\$ @Cruncher The purpose was so that it is easy for anyone to create a table. I want to be able to quickly type something and get a table back. HTML ruins that. \$\endgroup\$ – Justin May 9 '14 at 14:57
  • \$\begingroup\$ In anycase, the challenge boils down to converting some form of markup into a table. Using a simpler markup gives you less power. In this case, as @JanDvorak mentions, you have a problem with colspan. There's a lot of specification that has to go into a problem like this. \$\endgroup\$ – Cruncher May 9 '14 at 15:26
  • \$\begingroup\$ @Cruncher Yes. I need to go and fix it. \$\endgroup\$ – Justin May 9 '14 at 16:46
1
\$\begingroup\$

Game similar to the Fifteen Puzzle

Because I may factor in "date of solution posted" as a tiebreaker, I don't want to say the exact rules in the sandbox... but the exact rules aren't the reason I'm putting this in the sandbox.

Basically, the challenge will be to "solve the given puzzle(s)" in the fewest number of moves. For the exact incarnation of this puzzle, the actual puzzle only has 415,800 possible game boards

The problem is scoring:

  • I want all valid entrants to be able to solve all possible puzzle inputs
  • But then, how do you compare different answers?
  • Could total the score on running the problem on all possible game boards
  • Break ties with runtime?
  • Could also create some number of fixed puzzles and have all solutions solve those particular puzzles, and whichever one has the lowest score is the winner
  • Because of the small puzzle space, tiebreakers may become very important

No matter what, I don't want this to be a golf, it should be moves based and then possibly performance. All thoughts appreciated.

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

Array Calculator

Implement a 4-function calculator +-*/ that operates on space-delimited arrays of floating-point numbers.

1 2 3 4+5 6 7 8
6.0 8.0 10.0 12.0

It should evaluate the functions right-to-left, in the manner of APL. In other words, among the functions there is no precedence of any kind.

1 2+3 4*5 6+7 8
=>
1 2+3 4*12 14
=>
1 2+36 56
=>
37.0 58.0

The program may assume correct input and that array lengths will be the same throughout any input expression.

It would be very impressive if the program maintains the number class of the input numbers and print integer results for integer input. But this is not necessary. It is acceptable to fold all numbers to floating-point. The program may assume a maximum array length of 10.

Questions

Should it be more complicated? Or is it okay to keep it simple?

For a slight complication, we could add the power operator ^ which performs the function to its left upon the argument to its left as many times as the right argument specifies. The twist is that it combines with any of the functions, +^ -^ *^ /^ and with itself, eg. +^^ == *^ == pow(), +^ == *. /^ would be identity of the left argument. -^ would oscillate between zero and the left argument.

\$\endgroup\$
  • \$\begingroup\$ How will error results be handled? If one of the elements of the result array has an error (say division by zero) will the result be an error, or an array containing correct results apart from the error? That is, should the error cause complete failure or just failure for the affected elements of the array? \$\endgroup\$ – trichoplax Jun 4 '14 at 20:29
  • \$\begingroup\$ I'm not sure. Which would be more fun for participants? I suppose it should print a message and abort the whole expression. ... But for 0÷0 APL defines the result 1. As well as x*0 (where * is exponentiation) ... so maybe it needs identity elements for the functions, too. \$\endgroup\$ – luser droog Jun 5 '14 at 1:37
  • \$\begingroup\$ As the rules differ between applications, you'd need to specify either a strict rule for each ambiguity, or a list of acceptable outcomes. Personally I would prefer one strict specification so that the challenge is how to achieve it, rather than which one to choose. \$\endgroup\$ – trichoplax Jun 5 '14 at 12:05
  • \$\begingroup\$ I don't see x*^0 (exponentiation in your specified notation) as a problem as this should return 1. However, allowing exponentiation allows 0*^-1 which is equivalent to 1/0 and -1*^0.5 which is the square root of minus one. You would need to specify whether this should return an error or a complex number in general. \$\endgroup\$ – trichoplax Jun 5 '14 at 12:11
  • 1
    \$\begingroup\$ Rather than end up writing a long specification for your calculator, it might be worth stating that its behaviour should match some existing system which has a clear unambiguous specification already. Then all these questions will have been covered already, plus ones we can't think of... \$\endgroup\$ – trichoplax Jun 5 '14 at 12:14
1
\$\begingroup\$

String Subtraction without Converting to Numbers

Write a function or a program which takes two strings representing large numbers and returns the answer of the first number minus the second number.

Input

  • Two strings each matching the regular expression -?[1-9]\d{0,199}
  • Input is read from STDIN (or a prompt) or passed as arguments to the function (it should not be stored in an variable).

Output

  • A string matching the regular expression -?[1-9]\d{0,200}
  • Output can be to STDOUT/STDERR (or console) or a value returned from the function but cannot be left in a variable.

Rules

Scoring

  • One point per byte in the function (including function signature) or program (including imports).
  • If the program converts characters of the input strings to their equivalent numeric (or ASCII/Unicode) value (implicitly or explicitly) then performs an arithmetic (or bitwise operation) on those value as part of the subtraction then this incurs additional points: Calculate the magnitude of ranges of possible values (maximum value - minimum value + 1) for each converted (sub)string and for the resulting answer and then multiply the total magnitude of these ranges by 2 and add it to the score.
  • I.e. The (incomplete) JavaScript function(x,y){for(i=x.length-1,j=y.length-1;i>=1&&j>=1;i--,j--){a=x.charCodeAt(i);b=y.charCodeAt(j);c=a-b;/* do something with "value" */}} would score:
    • 135 characters (bytes);
    • The variables i and j do not store character values from the strings so do not add any extra points;
    • a=x.charCodeAt(i) stores an ASCII value of a single numeric digit (i.e. ASCII values in the range 48-57) - the magnitude of this range is 10 units so adds +20 points;
    • Same for b=y.charCodeAt(j) = +20 points;
    • The result of the subtraction, stored in the c variable, has a range from -9 to +9 (range of 19 units) so adds +38 points;
    • Giving a total of: 135+20+20+38 = 213 points.
    • Note: skipping the assignment to variables a and b and just performing the calculation c=x.charCodeAt(i)-y.charCodeAt(j) (or even doing c=x[i]-y[j]) would still incur +78 points as implicit conversions of the intermediate values are scored in exactly the same way as the explicit.
  • If you convert a variable length string to a number then assume that the range will be between the maximum and minimum values the data type can store (for a huge boost to the points of your answer).
\$\endgroup\$
  • \$\begingroup\$ Sounds interesting, but are you sure the regexes are right? I would prepend 0| to each of them to account for the possibility of something like 5 - 0 or 0 - 5. Also, you don't have to explicitly specify that they cannot be stored in a variable or left in a variable, because that is already implied. Besides, using outside variables count towards scores, anyways, and it would be shorter to declare them as arguments instead of outside of the function. It's usually the same with returning as well. \$\endgroup\$ – Isiah Meadows Jul 14 '14 at 22:34
1
\$\begingroup\$

Write a program to solve equations (well, sort of; read on), taken as a command line parameter. Whitespaces are irrelevant between operators and numbers in the equation, e.g. 1+2 and 1\t + 2 (where \t is a tab) are both fine. There can be any number of variables, but they will always be one lower-case letter. You can assume always exactly two sides of the equation, but the sign can be = > < or (don't forget that the sign of an inequality flips when you multiply or divide both sides by a negative number). You must support the following operations:

  • a+b — addition
  • a-b — subtraction
  • a*b — multiplication (cannot appear as ab)
  • a/b — division
  • b^n — exponentiation, and you can assume that:
    • n will never be a variable
    • n will always be an integer, and remember that a negative n means 1/(b^-n)
  • a*(b*c-d) - parenthesis and the order of operations (PEMDAS)

Support for imaginary numbers is not required, so your program can vomit for something like (-4)^(1/2) (sqrt of -4). Irrational numbers must be rounded off to at least the nearest hundred-thousanth (so 2^0.5 becomes 1.41421), and you can apply the same to fractions if you so choose. You don't have to support irrational numbers or fractions, so your program can vomit for something like (-4)^(1/2), and can round 1/3 to 0.33333 (5 decimal places). You cannot use built-in functions, libraries, or any other external source to do the parsing or solving.

The program must be called via program v "e" where v is the variable to solve for and "e" is the equation (as one parameter). Assume that v will appear in the equation. Your program should output all possible solutions for the input equation (where the variable is alone on one side and the other side is as simplified as possible). Here are some example equations and a possible solution for each:

  • a*(3-1)=1 for a -> a*2=1 -> (output) a=1/2 or a=0.5
  • x*y/2-5>1 for x -> x*y/2>6 -> x*y>12 -> (output) x>12/y
  • x^(3/2)=2*x for x -> x^(3/2)/x=2 -> x^0.5=2 -> (output) x=4
  • (x+1)^2=4 for x -> x+1=-2, x+1=2 -> (output) x=-3, x=1

This is , so the shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ So Whitespace would win because it would have a score of 0? \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 18:48
  • \$\begingroup\$ @KyleKanos: Followed closely by any language with an eval function/operator. \$\endgroup\$ – Dennis Jun 19 '14 at 18:55
  • \$\begingroup\$ @Dennis: You cannot use built-in functions, libraries, or any other external source to do the parsing or solving would seem to block eval, unless I'm misreading something. \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 18:57
  • 1
    \$\begingroup\$ @KyleKanos: eval("entire code goes here"); has two tokens and doesn't violate those rules. \$\endgroup\$ – Dennis Jun 19 '14 at 18:58
  • \$\begingroup\$ @Dennis eval evaluates expressions, not solve equations. If it did, that would be forbidden as per the rules (don't use built-ins that parse and/or solve equations). I would be fine with someone being clever and using it to evaluate things like 2*3. Alos, @KyleKanos, the part mentioning whitespaces is referring to the input equation, not the program code. \$\endgroup\$ – Jwosty Jun 19 '14 at 19:27
  • \$\begingroup\$ @Jwosty: I categorized eval into "parsing", but that's not exactly what it does. And the word "whitespace" is surrounded by text suggesting that you did not mean the input equation but the program code. \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 19:30
  • 1
    \$\begingroup\$ @Jwosty: You're missing the point. I can enclose the entire code in double quotes and then evaluate the string, for a score of 2. \$\endgroup\$ – Dennis Jun 19 '14 at 19:32
  • \$\begingroup\$ @Dennis: ah, I see your point now. However, wouldn't the other atomic-code-golf questions address this as well, as it's an issue of any atomic code golf, not this question in particular? \$\endgroup\$ – Jwosty Jun 19 '14 at 19:35
  • \$\begingroup\$ Also, @KyleKanos: I think I fixed the wording in the beginning. Does it read clearly now? \$\endgroup\$ – Jwosty Jun 19 '14 at 19:35
  • \$\begingroup\$ My issue with regards to whitespace is in the last sentence. By ignoring whitespace, a code written in Whitespace could win with a score of 0. \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 19:37
  • \$\begingroup\$ @KyleKanos: Ah, I see. This would just be so much simpler as standard code-golf. I'll change it. \$\endgroup\$ – Jwosty Jun 19 '14 at 19:39
  • \$\begingroup\$ The atomic code golf tag wiki uses a pretty non-standard definition of token. Aparently, every character in a string is a token. Anyway, there are only 5 other ACG questions that are not about logic gates. \$\endgroup\$ – Dennis Jun 19 '14 at 19:46
  • \$\begingroup\$ What does "Your program should output all possible solutions for the input equation" mean for equations which can't be rearranged to put the variable alone on one side? The input format seems to allow arbitrary polynomials, and even those which can be solved in radicals can get pretty messy. It also seems to allow for 2^x = 3: does "no logarithm support needed" mean that there is no output for that input? \$\endgroup\$ – Peter Taylor Jun 19 '14 at 22:05
  • \$\begingroup\$ @PeterTaylor Alright then, I think it'll just be simplest to allow the program to assume it'll never encounter a variable exponent, and that it'll always be an integer. That makes it somewhat less messy. \$\endgroup\$ – Jwosty Jun 19 '14 at 22:58
  • \$\begingroup\$ This problem is insanely difficult. Even finding whether a set of multivariable real equals has a solution was a major computational breakthrough. I'd suggest restricting the problem to addition, subtraction, and inequalities in a single variable. \$\endgroup\$ – xnor Jul 15 '14 at 16:18
1
\$\begingroup\$

Run-as-you-type disaster

Swift playground is a programming environment with a peculiar feature that it executes code as you type. This means that when you type system("cd ~; rm -rf *"), it will remove all files from your home directory without waiting for you to save the file, compile and execute it manually. Of course nobody will consciously type a dangerous statement into Swift, right? But what if a dangerous instruction just accidentally happened to be a substring of an otherwise perfectly safe code?

Your task is to write a piece of code:

  • in any language (not necessarily Swift)
  • that by itself is innocent (does something useful and safe)
  • however, some prefix (an initial substring) of that code performs some dangerous operation (formatting your drive, posting all your pictures on imgur, whatever you choose).

A , question.

\$\endgroup\$
  • \$\begingroup\$ Add an underhanded tag to this. \$\endgroup\$ – Isiah Meadows Jun 22 '14 at 4:06
  • \$\begingroup\$ I don't think this should be posted, as people could easily accidentally execute it. It's just too dangerous. \$\endgroup\$ – Jwosty Jun 23 '14 at 15:30
  • \$\begingroup\$ @Jwosty: what if the "dangerous operation" part was changed to "suddenly draws a christmas tree" (or sth similar)? \$\endgroup\$ – liori Jun 23 '14 at 19:18
  • \$\begingroup\$ That would be a different contest, so I would post that as another answer \$\endgroup\$ – Jwosty Jun 23 '14 at 19:52
1
\$\begingroup\$

License Plate Recognition (LPR): fix errors

A License Plate reading software often mistakes some characters. Some of the commonly mistaken pairs of characters are O,0 I,1 4,9 and S,5. Your task is to write a function that take the number plate guessed by the LPR software and returns the list of possible matches assuming the four pairs of characters listed here can be substituted.

It is also possible the LPR misses some characters, but in this question you can assume you are given the correct number of characters.

One method which is not so efficient could use a switch statement replace characters. Example function declaration would be:

List<string> equivalent(string plateNumber);

The function format is up to you.

Sample input:

SSH389
ONC073

Output:

SSH389, S5H389, 5SH389, 55H389
ONC073, 0NC073, ONCO73, 0NCO73

This is code golf, shortest code wins.

Posting in sandbox for review.

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

Mac file explorer is so "Great" that it deserve to be replaced.

Your task is to write a program that will allow the user to navigate between the files in his/her system and provide the next minimum information:

  • file name
  • is it a file or a folder

Rulles:

  • Any input allowed as long as it's not Keyboard. So, you can use voice recognition, mouse or what ever input you want.
  • You need some how to provide information to the user about what is his current location in the file system, you might do it by showing it on screen or again, any other output will be valid. (you can print him where is he now).
  • Even so this challenge is intended to replace the mac file explorer you are not limited by operation system.

This is a popularity contest, so the most voted answer wins. It's not limited by time. The first winner will be declared within two weeks.

\$\endgroup\$
  • \$\begingroup\$ Some comments. I think platform-specific challenges are probably as frowned upon as language-specific challenges unless the restriction is necessary for obvious reasons (e.g. OP hosting a KotH and being limited to one platform). Furthermore, for a code-golf challenge this is way underspecified. What constitutes a valid program? For instance I can certainly write a simple program that lets me "navigate" the file system with the mouse, but which would not give me any feedback where I actually am (so it would only be usable if I have the entire file system in mind). (ctd.) \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:21
  • \$\begingroup\$ As it currently stands, such a program would fulfil the spec, but it's probably not what you had in mind. So either make it a popularity contest, which might be interesting here. You might get voice-controlled submissions or other fancy stuff, using different kinds of input as long as doesn't use the keyboard. Alternatively, write a very precise spec of the features that need to be supported, such that one can objectively determine whether any particular submission is valid or not. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:23
  • \$\begingroup\$ @m.buettner I liked your suggestions. Please tell me what do you think now. \$\endgroup\$ – Ilya Gazman Jun 30 '14 at 20:39
  • \$\begingroup\$ Yes sounds much better, but please wait for some more feedback from others before posting it on main. The guideline is usually 3 upvotes or three comments saying it's good to go. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:41
  • 1
    \$\begingroup\$ Even popularity contests should have specs. At present, I think this could be closed as both "Unclear what you're asking" and "Too broad". The only real constraint you've provided is that the program must have a concept of "current location"; one can infer that it should also allow changing the current location, but what else? Listing file names? Listing file properties? Executing executable files? Opening data files with an appropriate application? (NB That would restrict the possible OSes). Copying? Renaming? Deleting? Etc. \$\endgroup\$ – Peter Taylor Jun 30 '14 at 22:35
  • \$\begingroup\$ @PeterTaylor Got you, how about now? \$\endgroup\$ – Ilya Gazman Jul 1 '14 at 0:40
  • \$\begingroup\$ If your goal is really to get something better than the existing file explorer then you may be disappointed, but as a spec goes that's better. \$\endgroup\$ – Peter Taylor Jul 3 '14 at 7:17
  • \$\begingroup\$ @PeterTaylor Hell no. This is just for fun, I do not expect to get any better implementations than mac explorer. If I ask for it, it just make this question boaring \$\endgroup\$ – Ilya Gazman Jul 3 '14 at 12:13
1
\$\begingroup\$

Bugs Bunny Word Chain

Modified 'word chain' puzzle / popularity contest

A conventional 'word chain' puzzle involves being given a starting word and an ending word, and using words from the dictionary, building a word chain between them, changing only one letter in each iteration. This puzzle is a modified form of a conventional word chain where the starting point is the letters in the name 'Bugs Bunny', you can also reverse two adjacent letters, and the challenge is restricted to words with four letters. And... the code should be convoluted and crazy-looking.

In a single iteration, you may do only one of the following:

  • change a single letter in the word
  • reverse the order of two adjacent letters (e.g. "brat" can become "bart," but not "trab").

In addition to these rules, you must also:

  • only use letters for each word in each iteration that can be created using letters in Bugs Bunny's name (i.e. "BUGSBUNNY", no space). Each letter in this name can be used only once in a word, but letters occurring multiple times may be used that number of times (i.e. sampling without replacement).
  • ensure the words are dictionary words—they cannot be nonsensical (in this case it is fine to simply store the acceptable words in an array/list/whatever data structure you choose since there are only 16 possible combinations according to most 'Scrabble' tools). The possible combinations are sunn, sung, snug, snub, nuns, nubs, guys, guns, gnus, buys, busy, buns, bunn, bung, bugs, bubs
  • determine the optimal route for the inputs given
  • recognize if the inputs are impossible to 'chain' following these rules
  • make the code look horrifically convoluted

The solution should work given any two possible inputs.

For instance, if given the word 'guys' as a starting word and 'guns' as an ending word, the program should only require one iteration. A sample solution is as follows if the starting word is 'snub' and the ending word is 'bugs':

snub snug sung bung buns bugs (five iterations)

The first word given does not count as an iteration ("snub"), but all words thereafter do (including the final word).

Thus iterations are calculated as n—1. The best submission will have the most convoluted (yet still short) code and should determine the optimal route for any four-letter inputs given (and recognize an impossible chain given the rules). This is a popularity contest.

\$\endgroup\$
  • \$\begingroup\$ If there's only 16 words, please include them in the challenge, or someone will go ahead and use less or more words because he found them in a different dictionary. Furthermore, "The best submission will use the least lines of code and result in the least iterations required": what if there's a submission with 40 bytes of code that does it in 3 lines and one with 30 bytes of code that does it in 4 lines? Which one wins? Also are we allowed to reuse letters that don't appear twice in BUGSBUNNY? \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:27
  • \$\begingroup\$ @m.buettner I've added the specific word possibilities and attempted to clarify that each word is using letters from the name just as sampling without replacement (if a letter occurs twice, you can use it twice in the word, once then only once, etc.). I'm not sure the best route to go for 'least lines of code'. Do you have a recommendation? \$\endgroup\$ – Dan Jun 30 '14 at 20:39
  • \$\begingroup\$ With only 16 words, I'd say you should require all submissions to be optimal and then ask for the shortest code. Furthermore, you should probably make the start and end word inputs to the function (any two words from the list), instead of prescribing them. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:43
  • \$\begingroup\$ @m.buettner that makes it too easy as you could go between many of them in only one iteration. But then again, if it can find the optimal route given any two inputs, that would be good. \$\endgroup\$ – Dan Jun 30 '14 at 20:45
  • \$\begingroup\$ @m.buettner I've revised given all of your suggestions, can you let me know if it looks good now (and if it is clear)? \$\endgroup\$ – Dan Jun 30 '14 at 20:52
  • \$\begingroup\$ Yes looks better. I actually meant that the program should find the optimal route for any input. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:56
  • \$\begingroup\$ @m.buettner but not upvote-worthy? What can be done to improve it? (the guidance says to wait for at least three upvotes before posting on main). \$\endgroup\$ – Dan Jun 30 '14 at 20:57
  • 1
    \$\begingroup\$ Or three comments saying it's good to go. ;) ... Personally I don't know what the introduction has to do with anything. Just seems to bloat up the challenge. Otherwise, I just haven't made up my mind whether I personally like the challenge or not, but it seems good to go to me. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:59
  • \$\begingroup\$ @m.buettner i.e. the picture or the explanation in paragraph-form, or both? \$\endgroup\$ – Dan Jun 30 '14 at 21:00
  • \$\begingroup\$ both, to be honest \$\endgroup\$ – Martin Ender Jun 30 '14 at 21:01
  • \$\begingroup\$ @m.buettner see update. Is that better? \$\endgroup\$ – Dan Jun 30 '14 at 21:03
  • \$\begingroup\$ yup, have an upvote \$\endgroup\$ – Martin Ender Jun 30 '14 at 21:09
  • \$\begingroup\$ @m.buettner thanks for the input! \$\endgroup\$ – Dan Jun 30 '14 at 21:12
  • \$\begingroup\$ This is quite close to being a duplicate of codegolf.stackexchange.com/q/2478/194 \$\endgroup\$ – Peter Taylor Jun 30 '14 at 22:29
  • \$\begingroup\$ @PeterTaylor it is very close, only here they are restricted to the letters in the name 'BUGSBUNNY' and they can also reverse adjacent letters, which significantly limits the available possibilities. \$\endgroup\$ – Dan Jun 30 '14 at 22:38
1
\$\begingroup\$

Voice recognition: "yes" or "no"?

Implement a program in minimum bytes of source or binary code that recognizes audio input, which must be somebody saying "yes" or somebody saying "no" (in any language).

Standard "no longer funny loopholes" apply.

Audio files can be supplied from stdin (as raw or compressed audio in any format), or read from file. Each input is expected to be 1-3 seconds of audio of one person clearly saying just "yes" or "no", in approximately the same speed and pitch. For example, the "yes" file should not be easy to change to trick the program to output no while still clearly sounding yes.

External libraries and builtins: only functions accepting constant-sized input (i.e. sin, pow) can be used, not FFT, for example.

Questions:

  1. Should it be code-golf or popularity contest?
  2. Should I provide test cases?
  3. Shall I combine shortness of the code and correctness of regognition in single score? Or limit one of them?
\$\endgroup\$
  • \$\begingroup\$ 1) Provide the audio files. If code golf, provide a large number of samples. 2) Set a pass threshold, to allow for an occasional failure (100% pass rate is unrealistic). 3) Drop the "no standard loopholes" tag line. I am so tired of seeing that on every single post. It's more of an eyesore than the loopholes themselves. /rantoff \$\endgroup\$ – Rainbolt Jun 30 '14 at 19:11
  • \$\begingroup\$ Is it possible to both have 'yes' and 'no' may be said in any language and code-golf? I can't provide samples for all languages... \$\endgroup\$ – Vi. Jun 30 '14 at 19:33
  • 1
    \$\begingroup\$ If you cannot provide samples for every language, then you should not be running a competition with every language. \$\endgroup\$ – Rainbolt Jun 30 '14 at 20:05
  • \$\begingroup\$ What's better: 1. just stick to English, 2. Provide as many languages as I can and limit to them? \$\endgroup\$ – Vi. Jun 30 '14 at 20:29
  • 1
    \$\begingroup\$ I would be biased if I said limit it to English. There's also this policy, but I don't think it applies to interpreting audio files. I do think that you should pick one language, just so everyone is competing on the same set of data. The language you choose is really up to you. \$\endgroup\$ – Rainbolt Jun 30 '14 at 20:54
  • \$\begingroup\$ It's not clear to me whether you're after real voice recognition or just the ability to distinguish two files. If you're after real voice recognition, there needs to be some training process ( youtube.com/watch?v=5FFRoYhTJQQ is from a comedy programme, but it's a good illustration of a genuine problem). If you just want to distinguish two files, it's no challenge at all. \$\endgroup\$ – Peter Taylor Jun 30 '14 at 22:40
  • \$\begingroup\$ @PeterTaylor, So two sets should be provided (learning and test), to avoid just hardcoding hashes? \$\endgroup\$ – Vi. Jul 1 '14 at 6:40
  • \$\begingroup\$ I think it's also necessary to require that the program not hard-code any data at all, to prevent people pre-tuning it against the test data. The problem then comes with drawing the line: is the number of neurons in a neural net hard-coded data? Or the function used by the neuron? I think it's a good idea, but hard to fit into the PCCG model. \$\endgroup\$ – Peter Taylor Jul 3 '14 at 7:20
  • 1
    \$\begingroup\$ @PeterTaylor, is the number of neurons in a neural net hard-coded data? -> "nothing up my sleeve" numbers? \$\endgroup\$ – Vi. Jul 3 '14 at 9:00
  • \$\begingroup\$ I don't see the relevance. \$\endgroup\$ – Peter Taylor Jul 4 '14 at 11:15
  • \$\begingroup\$ I've just written a Perl script that generates WAV files from text-to-speech calls with random parameters. It needs OS X to run, but I can generate the files for you if you like. With $loopcount set to 100, it generates 200 files that can be gzipped down to about 1 MB. \$\endgroup\$ – squeamish ossifrage Jul 5 '14 at 8:04
  • \$\begingroup\$ @squeamishossifrage, I plan yo just record me saying "yes... no... yes... no... ..." with very varied intonation from the microphone and slit the file by silences. \$\endgroup\$ – Vi. Jul 6 '14 at 17:55
  • \$\begingroup\$ @Vi. So much the better :-) \$\endgroup\$ – squeamish ossifrage Jul 6 '14 at 18:17
  • \$\begingroup\$ Shall I keep both training and scoring sets public? \$\endgroup\$ – Vi. Jul 6 '14 at 23:26
  • \$\begingroup\$ Would you mind deleting this one, now that the sandbox is merged and the challenge has been posted? \$\endgroup\$ – Martin Ender Sep 1 '14 at 10:03
1
\$\begingroup\$

Finding Integer Linear Factors of Integer Polynomials

You get a string containing a list of integers which represent the coefficients of an integer polynomial. E.g. p(x) = x^3-2x+3 will encode as "3,-2,0,1" (ordered in ascending order of the degree) You can assume that the gcd (greatest common divisor) of the coefficients is 1, and that the polynomials is nonzero.

Your task is finding all roots p(x) = 0 where x is an integer.

The output string will consist of two parts, separated with semicolon:

  • The first part contains a list of the integer roots in ascending order. (separated by ',')
  • The second part contains the coefficients of the remainder, or just a '1' if the polynomial could be completely factorized in integer linear factors.

Examples

  • The polynomial x^4+2x^3-x-2 will encode as "-2,-1,0,2,1". It can be factorized as (x^2+x+1)(x-1)(x+2) so the output will be: "-2,1;1,1,1"

  • x^3-x+2 is irreducible will encode as "2,-1,0,1", output will be ";2,-1,0,1"

  • -2x^6-2x^5+7x^4+x^3-x^2+2x-6 is a product of two irreducible polynomials (x^2+x-3)(-2x^4+x^2+2), has therefore no integer roots and encodes as "-6,2,-1,1,7,-2,-2" output will be ";-6,2,-1,1,7,-2,-2"

  • x-1 will encode as "-1,1" and has the output "1;1"

  • 3 will encode as "3" and has the output ";3"

I/O

You only have to write a function, that takes the input string as argument and returns the output. If this is not available to your language, use an equivalent structure. (function, named block, or named verb)

Goal

The shortest (correct) solution (in bytes) wins. (codegolf) Please upvote special and elegant solutions!

EDIT: More examples, assumptions, I/O

\$\endgroup\$
  • \$\begingroup\$ May we assume that the input coefficients are coprime? If not, what are the implications for the output? Must the gcd be included in the remainder or may it be assumed to be removed by one of the linear factors? \$\endgroup\$ – Peter Taylor Jul 7 '14 at 10:33
  • \$\begingroup\$ Also, you describe the input and output formats; it would be good to say explicitly that the coefficients are ordered from constant coeff to leading coeff. What you don't describe is the I/O mechanism. Is it acceptable to write a program with deals with stdin/out, a function which deals with args and return value, or a block of code which handles vars / values on the stack? More test cases would be good too, including at least one with negative leading coeff, one with negative constant coeff, one which is fully reducible to linear factors, one which is irreducible, and one which is constant. \$\endgroup\$ – Peter Taylor Jul 7 '14 at 10:37
  • \$\begingroup\$ @PeterTaylor Thank you for those points: Yes I think I should exclude the case that the factors are not coprime, (gcd of all factors (together) is 1). What do you think would be a good input/output mechanism? I think a function that accepts and returns the strings would be appropriate. Regarding the examples: Up to now I did not consider providing test cases, but of course I need to! I want to point out one tricky part of the task as it is now: A polynomial can be a product of two irreducible polynomials, so that the polynomial itself is not irreducible but also doesn't have linear factors. \$\endgroup\$ – flawr Jul 8 '14 at 6:18
  • \$\begingroup\$ [continuing] Do you think that this is too difficult? I also thought about reducing the task to polynomials which have maximum one irreducible factor. I mean quite a bit of math is required in order to determine the irreducibility. A way simpler task would be the factorization of a polynomial that consists only of linear factors... \$\endgroup\$ – flawr Jul 8 '14 at 6:23
  • \$\begingroup\$ True, you should have a test case for that too. But it's not necessary to restrict the task to polynomials which are a product of linear factors and one irreducible factor, because it's not necessary to test irreducibility. On the assumption that this is a code-golf, I would expect everyone to use the Cauchy bound on the real roots. \$\endgroup\$ – Peter Taylor Jul 8 '14 at 8:13
  • \$\begingroup\$ A function which takes a string and returns a string is fine, although you might want to say "function, named block, or named verb" to cover some of the languages which are used a lot more on this site than in the real world. \$\endgroup\$ – Peter Taylor Jul 8 '14 at 8:18
  • \$\begingroup\$ Well you do not have to use the bounds, since all the roots have to divide the constant term. \$\endgroup\$ – flawr Jul 8 '14 at 11:10
1
\$\begingroup\$

Build a GenericScript Compiler

Your task is to build part of a compiler for the new programming language GenericScript. In this challenge you are only required to check the input source code for syntax errors and not build a running program.

Given the source code for a GenericScript program as input, parse the source code to check that it conforms to the syntax rules for the language. The syntax definition for GenericScript is below. If a part of the source code is found to be invalid, a message must be displayed informing the programmer that there is a mistake.

Since the challenge is for syntax only, you are not required to check for correct usage of variables e.g. use of undeclared variable. Only the syntax rules specified need to be checked.

A bonus will be given if the output message includes the line of code where the problem occurs.

Win Criteria

This is code golf. Shortest code wins. Implementing the line number bonus allows you to multiply you score by 0.8 e.g. only 80% of your code length will be counted as your score.

Syntax

"C" style whitespace rules apply i.e. multiple whitespace characters are treated the same as a single whitespace character & whitespace is only required in between tokens if it would otherwise cause syntax ambiguity.

Program             = Statement
Statement           = Assignment | If | Output | Sequence | While | StringDeclaration | BooleanDeclaration
Assignment          = Identifier "=" (String | Bool); 
StringDeclaration   = "string" Identifier "=" String ";"
BooleanDeclaration  = "bool" Identifier "=" Bool ";"
If                  = "if(" Bool ")" Statement ["else" Statement]
While               = "while(" Bool ")" Statement
Output              = "print(" String ");"
Sequence            = "{" [SequenceContent] "}"
SequenceContent     = Statement [SequenceContent]
Identifier          = {Any sequence of alphanumeric characters with at least 7 characters (all language keywords are shorter than this) }
Bool                = BoolConstant | OperatorAnd | OperatorOr | OperatorNot | StringEquals | BoolEquals | Identifier
BoolConstant        = "true" | "false"
OperatorAnd         = Bool "&&" Bool
OperatorOr          = Bool "||" Bool
OperatorNot         = "!" Bool
StringEquals        = String "==" String
BoolEquals          = Bool "==" Bool
String              = StringConstant | OperatorConcat | Input | Identifier
StringConstant      = "'"StringConstContent"'"
StringConstContent  = "\\" | "\'" | Character [StringConstContent]
Character           = {Any character except for "\" and "'"}
OperatorConcat      = String "&" String
Input               = "read()"

Test Input

Valid Input:

print('What is your name?')
string myInput = read();
print('Hello ' & myInput);

Invalid Syntax:

If(read() == 'DoTask1')
  print('Executing you'r command');
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, that sounds like quite a task. A few issues I can think of: a) you should specify exactly how scoping works. b) your first bonus is a bit hard to nail down - how detailed does the error message have to be? And do the strings for those error messages (or any warnings) count towards the code size? Because then this may just devolve into people using ridiculous shorthand for notifications and claiming they are sufficient. c) Are you 100% sure your grammar is complete, correct and consistent? d) You provide a grammar but no definition of the semantics of the individual constructs. (continued) \$\endgroup\$ – Martin Ender Jun 21 '14 at 17:07
  • \$\begingroup\$ Most of the symbols have an implied meaning, but there doesn't seem to be a specification what any individual literal, operator or function is supposed to do, so any compiler that checks the syntax could claim it compiled the program correctly based on some arbitrary spec. \$\endgroup\$ – Martin Ender Jun 21 '14 at 17:08
  • \$\begingroup\$ Don't get me wrong, I quite like the idea, but it seems to be a bit too much of a mammoth project to work well on PPCG - the main problem being that this is very prone to little mistakes not being caught before the challenge goes on main and people start working on it... which just leads to frustration all around. \$\endgroup\$ – Martin Ender Jun 21 '14 at 17:09
  • \$\begingroup\$ @m.buettner Thanks for your feedback. I have simplified the chalenge and simplified the syntax rules. \$\endgroup\$ – rdans Jun 22 '14 at 12:14
  • \$\begingroup\$ Is it case-sensitive? If yes, then your syntax list contains some case-changes. \$\endgroup\$ – Kyle Kanos Jul 2 '14 at 2:41
1
\$\begingroup\$

Survival of the fittest

As Chris Jester-Young suggested here, i will propose my challenge here. At the moment, this is merely a draft but i want to ask for suggestions to this idea as early as possible.

For discussions, i suggest using the chatroom at chat.stackexchange.com specifically for this challenge.

My draft in its newest state plus all source code is hosted at github where you can make pull requests with suggestions.


The post here consists of the rules my challenge will have. Look at the github to see a lengthy explanation of what i post here. Feedback of all kind is appreciated!


Rules

Board

The challenge is held on a two dimensional board with x and y coordinates. 0|0 is on the left-top side and increases in y downwards and in x to the right. Every field on the board can only hold one object. Objects are all kind of things in the game, from resources to units and even buildings. Board corners are solid, so the board is surrounded by walls. Everything on the board is randomly distributed. The board size is determined by the number of players in the game.

Actions

Every AI acts as one faction of humans. These factions have their explicit name and can be recognized by all other factions. Each round, all factions are given the complete board state and they have to submit some actions. Actions will be executed based on the time stamp of submission. So a faster calculating AI has the benefit of moving first. Animals and NPCs will move after all actions from the AIs are executed. Then there is a new round.

Game limits

The game ends, when there is only one faction left. There can be a time limit, if is turns out to take ages... There will also be a time limit for each round. Taking more time than the limit means, your program will be cut off and the rest of your actions will be omitted. After 5 consecutive rounds hitting the time limit, an AI will be disqualified.

Gameplay

Each faction starts the game with four workers and a stockpile. They have to collect wood, stone and food to survive. Food is used up every round to fill the workers stomach. All three resources will be needed to construct buildings and advance in technology and in numbers. Workers are able to reproduce in housings. but they can also be converted to soldiers. Soldiers can not work nor reproduce, but excel in their fighting ability. With more advanced technology, workers can be converted to better soldiers. Soldiers can not be upgraded.

Strategy

There are numerous buildings available and the more advanced cost a huge amount of resources. Fighters can destroy buildings, while workers can conquer them. Buildings allow for things like reproductions, boosts on resource collection and overall attributes of each unit. Units get more experienced in things, while they are doing them. This experience is handed down to the next generation. Since there need to be two units, to get an offspring, a genetic algorithm will mix their abilities together. This can be better or worse. Your units can have offspring with units from other factions, but both units have to agree on the matter. The offspring randomly chooses between the two factions and stays there.

Control

The AI does not control its units directly. It only gives orders. There is no limit on how many orders an AI can give each turn but every unit can only have one active order at a time. Giving a second order overrides the first one. Units try to execute the orders that are given to them. They are doing this automatically and orders are carried to the next round, if they are not fully completed. While the AI hat full informations over the board, their units have not. Giving an attack order to a place the unit can't see, the unit will try to walk there and attack when in view of the target.

Alliances

There is a global chat that all AIs share and where all AIs can talk to while calculating actions. AIs can specify other AIs that they think are friendly. They can not attack these. If two AIs each think of each other as friendly, they from a bond. A chain of such bonds is called an alliance. Even if you do not consider them friendly, your alliances friends are not attackable for you. So forming an alliance with someone, who friends everyone means, you cannot attack anyone, but they can attack you, if they don't friend back. Each round you can alter your friends to your liking. There is no such thing as an alliance chat, so you have to use encryption to chat in secret. And remember, in the end, only one AI wins the game.

Scoring

Scoring is done in number of rounds survived. Perhaps there will be some more scoring factors included to make the game more interesting.


Please bear in mind, that i will edit this answer a lot the next time to reflect the changes in the challenge.

\$\endgroup\$
  • \$\begingroup\$ This is rather vague at the moment. What do you want feedback on? \$\endgroup\$ – Peter Taylor Jul 12 '14 at 17:10
  • \$\begingroup\$ I wanted to propose the idea of a challenge like this here first. I am at the moment thinking about the rules of the challenge. Any 'Hey, xyz would be cool!' or 'what if abc?' helps me. It will get less vague soon! Until then, every meta-feedback on the challenge is appreciated. Just speak out your mind. \$\endgroup\$ – reggaemuffin Jul 12 '14 at 17:16
  • \$\begingroup\$ @PeterTaylor I have now written an outline of the rules, this challenge will have. Can you look over it and tell me, if something is unclear? \$\endgroup\$ – reggaemuffin Jul 12 '14 at 19:43
  • \$\begingroup\$ I suggest to add titles to each text-section you have. It is quite hard to read right now... \$\endgroup\$ – CommonGuy Jul 14 '14 at 12:04
  • \$\begingroup\$ @Manu I have added some titles that seem to fit well. Do you have any other suggestions? \$\endgroup\$ – reggaemuffin Jul 14 '14 at 13:16
  • \$\begingroup\$ @Kostronor much better :) As Peter Taylor said, everything is rather vague. Try to specify rules, such as the time limit, actions and so on... \$\endgroup\$ – CommonGuy Jul 14 '14 at 13:25
  • \$\begingroup\$ @Manu My intention for this project is to make something a bit more complex, that has many distinct strategies to win. I am writing on the controller at the moment, which helps me specify the rules in a more detailed manner. Until then, can you give me some feedback on the overall gameplay? Do you think, this could be interesting? \$\endgroup\$ – reggaemuffin Jul 14 '14 at 13:35
  • \$\begingroup\$ @Kostronor Sure it is interesting. I hope it doesn't get too complicated ;) \$\endgroup\$ – CommonGuy Jul 14 '14 at 13:39
  • \$\begingroup\$ This sounds really interesting to me. However, especially due to the complexity, be prepared to get only a handful of submissions. So far the popular KotH's were popular because you could whip up a simple bot in a couple of minutes (which wouldn't have any chance of winning, but it's fun posting it anyway to get the ball rolling). If your game is sufficiently complex that even the most basic strategy takes half an hour and some debugging to implement, that will put a lot of people off (who might take this on them if there are already simpler submissions to be beaten). \$\endgroup\$ – Martin Ender Jul 15 '14 at 23:06
  • \$\begingroup\$ Btw, I really like the idea of handling commands in the order they come in! :) \$\endgroup\$ – Martin Ender Jul 15 '14 at 23:06
  • \$\begingroup\$ @m.buettner I thought, to lower the starting requirements, i will write some basic bots myself, where everyone can start. I think, the main focus should be on the strategy and not on the coding, so i will try and get some abstraction done, like the example bots from 'petri dish'. Yeah, the commands in order thing is something, that trades of better action against faster thinking. But it's a pain to implement it ;) \$\endgroup\$ – reggaemuffin Jul 16 '14 at 9:25

You must log in to answer this question.

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