title: Are these trees isomorphic?

text:
# Question
Title: Are these trees isomorphic?
## Introduction

In this challenge, your task is to write a program that decides whether two given trees are isomorphic. A tree means a directed acyclic graph where every node has exactly one outgoing edge, except the root, which has none. Two trees are isomorphic if one can be transformed into the other by renaming the nodes. For example, the two trees (where every edge points up)

```
  0       0
 /|\     /|\
1 3 4   1 2 5
|\       /|
2 5     3 4

```

are easily seen to be isomorphic.

We encode a tree as a list `L` of nonnegative integers in the following way. The root of the tree has label `0`, and it also has nodes `1,2,...,length(L)`. Each node `i > 0` has an outgoing edge to `L[i]` (using 1-based indexing). For example, the list (with the indices given under the elements)

```
[0,0,1,3,2,2,5,0]
 1 2 3 4 5 6 7 8

```

encodes the tree

```
  0
 /|\
1 2 8
| |\
3 5 6
| |
4 7

```

## Input

Your inputs are two lists of nonnegative integers, given in the native format or your language. They encode two trees in the manner specified above. You can assume the following conditions about them:

1. They are not empty.
2. They have the same length.
3. Each list `L` satisfies `L[i] < i` for all (1-based) indices `i`.

## Output

Your output shall be a truthy value if the trees are isomorphic, and a falsy value if not.

## Rules and scoring

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There are no time restrictions, but built-ins that decide tree or graph isomorphism are disallowed.

## Test cases

Truthy instances

```
[0] [0]
[0,1,2,1] [0,1,1,3]
[0,1,1,3,3] [0,1,2,2,1]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,4,2,1]
[0,1,2,3,1,2,3,0,8] [0,1,0,3,3,4,4,7,7]

```

Falsy instances

```
[0,0] [0,1]
[0,1,2,0,3,3,4] [0,1,2,3,0,4,3]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,5,2,1]
[0,1,1,0,1,3,2,1,5] [0,1,0,3,3,3,2,5,2]
[0,1,2,3,1,2,3,0,8] [0,1,0,1,4,4,5,6,6]
[0,1,0,2,0,3,0,4,0,5] [0,0,2,1,0,3,4,0,0,9]

```

# Answer
> 2 votes
# Mathematica, 48 bytes

```
SameQ@@(Sort//@(0(0//.PositionIndex@#))&/@{##})&

```

It's even shorter than the solution that uses `IsomorphicGraphQ`:

```
IsomorphicGraphQ@@(Graph@*MapIndexed[#->Tr@#2&]/@{##})&

```

# Answer
> 6 votes
# Python, 83

The anonymous function on the 2nd line is my solution.

```
f=lambda l,i=0:sorted(f(l,j+1)for j,e in enumerate(l)if e==i)
lambda a,b:f(a)==f(b)

```

`f` returns a canonized form of a subtree which is a sorted list of its canonized children. Then we must simply check if the canonized forms of each tree are equal.

---
Tags: code-golf, array, graph-theory, decision-problem
---


title: Layout my tiles for me

text:
# Question
Title: Layout my tiles for me
I'm retiling my kitchen with different coloured tiles. In fact, it's going to have at least 2 colours - and 26 colours as a maximum.

But, I'm fussy. I want this wall to look random, but sometimes random isn't random enough.

So, when I lay out my tiles, I don't want to have any the same colour next to each other in the 4 Cartesian directions. Diagonally adjacent is (of course) fine.

Acceptable:

```
┌───┐
│ A │
└───┘

```

```
┌───┬───┬───┐
│ A │ B │ A │
├───┼───┼───┤
│ B │ A │ B │
└───┴───┴───┘

```

```
┌───┬───┬───┐
│ A │ B │ C │
├───┼───┼───┤
│ C │ A │ B │
└───┴───┴───┘

```

Unacceptable:

```
┌───┬───┬───┐
│ A │ B │ A │
├───┼───┼───┤
│ A │ A │ B │
└───┴───┴───┘

```

```
┌───┬───┬───┐
│ A │ C │ C │
├───┼───┼───┤
│ C │ A │ B │
└───┴───┴───┘

```

Given input in the form `A B N` where `A` is the width, `B` is the height and `N` is the number of colours - an integer from 2 to 26 - you need to output a grid like so:

Input:

```
5 6 4

```

Example output:

```
A B C D A
B A D A C
A D C D A
B C B A B
D A D C A
B C A D C

```

The input will be given as a) 3 arguments to a function or b) as 3 separate input statements or b) as `A B N`. Input will always be valid.

All colours have to be used and all valid tilings have to have a non-zero probability of being generated.

This is so the shortest code wins.

# Answer
## Python 2, ~~151~~ 149 bytes

```
from random import*
W,H,N=input()
L='x'*W
exec"M='';exec'M+=sample(set(map(chr,range(65,65+N)))-{L[len(M)],M[-1:]},1)[0];'*W;L=M;print' '.join(L);"*H

```

Takes input comma-separated via STDIN, e.g. `10, 10, 2`.
> 1 votes

# Answer
# CJam, ~~53~~ ~~52~~ 51 bytes

```
q~:L,'Af+a*a*{_::mR_:|,L<\_z:O|N*2ew::=|:|}g;OSf*N*

```

This will take a *long* time if **AB** is too large or **N** is too small.

Try it online in the CJam interpreter.
> 1 votes

# Answer
# Python2, 177 bytes

```
from random import *
W,H,N=input()
A,l={chr(c)for c in range(65,65+N)},[" "*W]
for h in range(H):
 s=""
 for c in l[h]:s+=sample(A-{s[-1:],c},1)[0]
 l+=[s]
print"\n".join(l[1:])

```
> 0 votes

---
Tags: code-golf, random, grid
---


title: Pentomino Validator

text:
# Question
Title: Pentomino Validator
As someone who can't be bothered to look at their pentominos to see if it makes a rectangular shape, I've decided to make you write a program that does it.

# Your task

Given some input split by newlines containing 12 unique characters, decide if it is a valid solution.

A valid solution MUST

* Have 5 of each character (except newlines)
* Each set of characters must be fully connected
* Each set of characters must have a unique shape
* Be in a regular rectangular shape

If it is a valid solution, output a truthy value, otherwise output a falsy value.

Your program may be a function or a full program but must take the input from stdin and output to stdout.

## Test cases

Valid solutions

```
000111
203331
203431
22 444
2   46
57 666
57769!
58779!
58899!
5889!!

00.@@@ccccF111//=---
0...@@c))FFF1//8===-
00.ttttt)))F1/8888=-

```

Invalid configurations

```
invalid (doesn't contain 12 unique characters)

111112222233333444445555566666
77777888889999900000qqqqqwwwww (Each set has the same shape)

1234567890qw
w1234567890q
qw1234567890
0qw123456789
90qw12345678 (None of the characters are connected)

1234567890qw (Not 5 characters in every set)

1111122222333334444455555666666
77777888889999900000qqqqqwwwwww (More than 5 characters in some sets)

00
0
00.@@@ccccF111//=---
 ...@@c))FFF1//8===-
  .ttttt)))F1/8888=- (Doesn't form a rectangular shape)

```

# Answer
> 3 votes
# JavaScript (ES6), ~~237~~ ~~235~~ 222 bytes

```
f=p=>(m=[],s=[],d=0,l=p.indexOf`
`+1,[...p].map((c,i)=>(i+1)%l&&!m[i]?g=d-2<s.indexOf((t=a=>m[a]|p[a]!=c?r=0:(m[a]=y.push(a),n=a<n?a:n,t(a+1)+t(a-1)+t(a+l)+t(a-l)+1))(n=i,y=[])!=5?g=0:s[d++]=y.map(a=>r+=a-n)|r):0),d==12&g)

```

2 bytes saved thanks to @DankMemes!

## Usage

```
f(`000111
203331
203431
22 444
2   46
57 666
57769!
58779!
58899!
5889!!`);
=> true

```

## Explanation

A couple of notes about this solution:

* It's possible this answer is not valid. It does not actually check if rotated pentominoes are the same shape, however I tried but could not find a valid pentomino rectangle that meets the requirements in the rules and includes two or more of the same shape rotated. But I'm no pentomino expert so if you find a valid combination that this fails with, let me know.
* The rules also require answers to use `STDIN` and `STDOUT` for input and output but `prompt()` is only designed for single line input and my (Windows) computer automatically puts `\r\n` characters at every new line when pasting so I made it a function that accepts a string.

```
f=p=>(
  m=[],                      // m = map of checked characters
  s=[],                      // s = list of shapes found (stored as integer)
  d=0,                       // d = number shapes found
  l=p.indexOf`
`+1,                         // l = length of each line (including newline character)
  [...p].map((c,i)=>         // iterate through each character of the input
    (i+1)%l&&                // skip newline characters
      !m[i]?                 // skip the character if it has already been mapped
        g=                   // g = pentomino is valid
          d-2<s.indexOf(     // check if shape already existed before just now
            (t=a=>           // t() checks if character is part of the shape then maps it
              m[a]|          // skip if character is already mapped
                p[a]!=c      //    or if the current character is part of the shape
              ?r=0:(
                m[a]=        // mark the character as mapped
                  y.push(a), // y = list of shape character indices
                n=a<n?a:n,   // n = minimum index of all characters in the shape
                t(a+1)+      // check and map adjacent characters
                t(a-1)+
                t(a+l)+
                t(a-l)+
                1
              )
          )(n=i,y=[])
            !=5?g=0:         // make sure there are only 5 characters in the shape
            s[d++]=          // add the shape to the list
              y.map(a=>      // sum of (index of each character in the shape - minimum
                r+=a-n)|r    //     index) = unique integer representing the shape
        ):0
  ),
  d==12&g                    // ensure there is 12 shapes and return the 'is valid' result
)

```

---
Tags: code-golf, string, decision-problem
---


title: Golf Me An OOP!

text:
# Question
Title: Golf Me An OOP!
# Golf Me An OOP!

Two important components of object-oriented programming are inheritance and composition. Together, they allow for creating simple yet powerful class hierarchies to solve problems. Your task is to parse a series of statements about a class hierarchy, and answer questions about the hierarchy.

## Input

A series of statements and questions about a class hierarchy, read from a file or standard input, whichever is best for your language. If you use the file option, the filename will be passed as the first argument to your code (function argument or command line argument, whichever you choose). The format is as follows:

```
<statement> : <name> is a <name>. | <name> has a <name>.
<question> : Is <name> a <name>? | Does <name> have a <name>?
<name> : a-z | A-Z | sequence of alphanumerics or underscores, starting with a letter

```

The input will always be statements, then questions. All class names will begin with an uppercase English letter (`A-Z`), and all member names will begin with a lowercase English letter (`a-z`). All names are case-sensitive - `ABC123` is not the same class as `Abc123`.

There will not be any cyclical inheritance - if `B` inherits from `A`, `A` will not inherit from `B` or any of `B`'s children.

Only class names will be a part of a hierarchy - statements such as `foo is a bar.` or `document has a name.` will not occur.

## Output

A series of truthy or falsey values, as answers to the queries, written to standard output or as the return value of your function. If you do not have enough information to answer a question (e.g. questions that involve names you have not seen in the statements), answer with a falsey value.

## Test Cases

Case 1:

Input:

```
B is a A.
C is a B.
A has a foo.
Does B have a foo?
Is C a A?
Is D a A?

```

Output:

```
True
True
False

```

Case 2:

Input:

```
Cop is a Person.
Criminal is a Person.
Sheriff is a Cop.
Crooked_Cop is a Cop.
Crooked_Cop is a Criminal.
BankRobber is a Criminal.
Cop has a badge.
Criminal has a criminal_record.
Person has a name.
Is Crooked_Cop a Person?
Does Criminal have a name?
Is Crooked_Cop a BankRobber?
Does Person have a potato?
Is Cop a Cop?

```

Output:

```
True
True
False
False
True

```

## Rules

* You may answer with a function or a program
* Standard loopholes are forbidden
* This is , so shortest correct answer in bytes wins
* The winning answer will be chosen in one week

Good luck, and may the OOP be with you!

# Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 61097; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
```

# Answer
> 12 votes
# CJam, 59 bytes

```
q_'.e=\N/{)'?=\S/>_,(%}%/(__,*{(2$z~@f=.*\m*|}/ff{1$e=>:=N}

```

This finishes instantly for both test cases.

It either prints the second name name of the question or `1` (both truthy), or `0` (falsy).

Try it online in the CJam interpreter.

### Idea

Because of the distinction between classes and members, the challenge boils down to creating a preorder for which the input provides a partial definition.

We define that *x**y* iff *x* is a *y* or *x* has a *y*.

For the first test case, the input states that *B**A*, *C**B* and *A**foo*. Because of transitivity, we also have *B**foo*, *C**A* and *A**foo*. Also, because of reflexivity, *x**x* is always true.

For a given input, we thus can extract the partial definition of ≺ from the statements, apply transitivity a sufficient amount of times to complete the definition of ≺ and finally answer the questions.

### Code

```
q_     e# Push all input from STDIN and a copy.
'.e=   e# Count the number of dots/statements (C).
\N/    e# Split the original input at linefeeds.
{      e# For each line:
  )'?= e#   Pop the last character and check if it is a question mark.
       e#   Pushes 1 for '?', 0 for '.'.
  \S/  e#   Split the modified line at spaces.
  >    e#   Remove the first chunk ("Does" or "Is") for questions.
  _,(% e#   Keep the first and last element of the resulting array.
}%/    e# Split the line array into chunks of length C.
(_     e# Extract the first chunk (statements) and push a copy.
       e# The original becomes an accumulator for ≺.
_,*    e# Repeat the statements C times.
{      e# For each of the repeated statements:
  (    e#   Shift out the first name.
       e#     ["w" "x"] -> ["x"] "w"
  2$z~ e#   Copy the accumulator, zip it and dump.
       e#     [["x" "y"] ["z" "w"]] -> ["x" "z"] ["y" "w"]
  @f=  e#   Rotate the shifted out name on top and check for equality.
       e#     ["y" "w"] "w" -> [0 1]
  .*   e#   Vectorized string repetition.
       e#     ["x" "z"] [0 1] -> ["" "z"]
  \m*  e#   Swap the result with the shifted array and apply Cartesian product.
       e#     ["" "z"] ["x"] -> [["" "x"] ["z" "x"]]
       e#   This accounts for transitivity; we had ["w" "x"] and ["z" "w"],
       e#   so now we have ["z" "x"].
  |    e#   Perform set union with the accumulator to add the new pairs.
}/     e#
ff{    e# For each of the questions on the bottom of the stack.
  1$e= e#   Count the occurrences of the question pair in the accumulator.
  >    e#   Remove 0 or 1 elements from the question pair.
  :=   e#   Check for equality.
       e#   If the question pair occurs in the accumulator, this pushes the
       e#   second name of the question pair. Otherwise, it pushes 1 if the
       e#   names are equal (to account for reflexivity) and 0 otherwise.
  N    e#   Push a linefeed.
}      e#

```

# Answer
> 7 votes
# Python 3, ~~431~~ ~~331~~ 308 bytes

```
o={}
f={}
def h(z,f):
 if z not in o:f[z]=[z];o[z]=[]
while 1:
 g=input().split(' ');r=2;l=g[-1][:-1]
 if'.'in g[3]:
  if'i'in g[1]:h(g[0],f);h(l,f);f[g[0]]+=f[l]
  if'h'in g[1]:o[g[0]]+=l,
 else:
  if'I'in g[0]:r=any(l in z for z in f[g[1]])
  if'D'in g[0]:r=any(l in o[z] for z in f[g[1]])
 if r<2:print(r)

```

---

This is the full version with comments

```
objects = {}
synonyms = {}

def createObject(name):
    """
    Create a object with `name` if is does not yet exist and start a synonym tree.
    """
    if name not in objects:
        synonyms[name] = [name]
        objects[name] = []

# use this to read from a file
# with open("questions.txt") as file:
#     for l in file:
        # print(">>> " + l, end='')
        # inArg = l.replace("\n","").split(" ")

while True: # to read from a file comment this
        inArg = input(">>> ").split(" ") # and this out

        out = -1

        if '.' in inArg[3]: # statement
            last = inArg[3].replace('.','')

            if 'i' in inArg[1]: # is a
                createObject(inArg[0])
                createObject(last)
                synonyms[inArg[0]] += synonyms[last]

            if 'h' in inArg[1]: # has a
                objects[inArg[0]] += [last]

        else:# question
            last = inArg[-1].replace('?','')

            createObject(inArg[1])
            if 'I'in inArg[0]: # Is a
                out = any([last in syn for syn in synonyms[inArg[1]]])

            if 'D'in inArg[0]: # Does have a
                out = any(last in objects[syn] for syn in synonyms[inArg[1]])

        if out != -1:
            print(out)

```

---

Output for test case #1:

```
True
True
False

```

Case #2:

```
True
True
False
False
True

```

I removed the debug commands for clarity in the main program, but if you would like to see them just look in the history

# Answer
> 3 votes
# JavaScript, ~~265~~ 263 bytes

```
for(o={};i=prompt().split(/\W/);)a=i[0],b=i[1],d=i[2],b=="is"?((o[a]=o[a]||{p:[],k:{}}).p.push(d),o[d]=o[d]||{p:[],k:{}}):b=="has"?o[a].k[d]=1:alert(o[b]&&(a>"E"?b==d|(c=n=>~(p=o[n].p).indexOf(d)|p.some(c))(b):(c=n=>o[n].k.hasOwnProperty(i[4])|o[n].p.some(c))(b)))

```

Enter a blank string to quit.

## Explanation

```
for(
  o={};                               // o = all objects
  i=prompt().split(/\W/);             // i = command as an array of words
)
  a=i[0],                             // a = first word
  b=i[1],                             // b = second word
  //c=i[2],                           // c = third word
  d=i[3],                             // b = fourth word
  //e=i[4],                           // e = fifth word

  // Case: <name> is a <name>.
  b=="is"?(
    (o[a]=o[a]||{p:[],k:{}})          // create the object if it does not exist
      .p.push(d),                     // add the parent to the object's list of parents
    o[d]=o[d]||{p:[],k:{}}            // create the parent if it does not exist
  ):

  // Case: <name> has a <name>.
  b=="has"?
    o[a].k[d]=1                       // set the specified property

  :
  alert(                              // display the responses to the questions
    o[b]                              // false if the queried object does not exist
    &&(

      // Case: Is <name> a <name>?
      a>"E"?                          // "Is" > "E" and "Does" < "E"
        b==d                          // check if it is itself
        |(c=n=>
          ~(p=o[n].p)                 // p = direct parents of current object
            .indexOf(d)               // check direct parents for the object
          |p.some(c)                  // check the grandparents
        )(b)

      // Case: Does <name> have a <name>?
      :
        (c=n=>
          o[n].k.hasOwnProperty(i[4]) // check if this object has the property
          |o[n].p.some(c)             // check it's parents for the property also
        )(b)
    )
  )

```

# Answer
> 3 votes
# Haskell, 157 bytes

```
o s=v(x 0#k)#(x 1#q)where(k,q)=break((=='?').l.l)(words#lines s)
x n w=(w!!n,init$l w)
v k(a,c)=a==c||or[v k(b,c)|b<-snd#(filter((==a).fst)k)]
(#)=map
l=last

```

Give the string to `o`. Not sure if making `x` and `v` ('extract' and 'verify') infixes cuts more than making `map` an infix, or if both is possible.

## EDIT: Explanation

So, `(#)` is how you define an infix operator, I use it just as a shorthand for `map`, applying a function to each element of a list. Resolving this and the other alias `l`, avoiding the 'direct-function-application'-operator `$` and adding even more parentheses and spacing things out, and with real function names we arrive at:

```
oop string = map (verify (map (extract 0) knowledge)) (map (extract 1) questions)
 where (knowledge,questions) = break ((=='?').last.last) (map words (lines string))

extract n wordlist = (wordlist!!n,init (last wordlist))

verify knowledge (a,c) = (a==c)
               || or [verify knowledge (b,c) | b <- map snd (filter ((==a).fst) knowledge)]

```

`map words (lines string)` is a list of word lists of each lines in the input string.

`(=='?').last.last` is a predicate indicating whether the last letter in the last word of a line is a question mark, i.e. whether the line is a question.

`break` breaks the list in a tuple of the first part without questions (all statements) and the part from the first question on (all questions).

`map`ping `extract n` on these takes out of each word list the elements we really want, the `n`th one (which in statements is the first word - so `n == 0`, and in questions is the second word - so `n == 1`) using the `!!` operator and the last one, from which we have to cut the last letter (either `'.'` or `'?'`) using `init`.

(Note that I completetely ignore capitalization, that's because I completely ignore the distinction between classes and members, members are just leafs of a tree constructed by the knowledge base (but not all leafs represent members, they may also be classes with neither subclasses nor members), in which every child node represents a subclass or member of what its parent node represents. I JUST REALIZED THIS IS A WRONG THING TO DO in cases not covered by OP. Will edit solution soon.)

Now, `map (extract 0) knowledge` and `map (extract 1) questions` are lists of tuples of names representing a subclass- or member-relationship of the first to the second.

The tuples in `map (extract 0) knowledge` are all true relationships, those in `map (extract 1) questions` are now mapped the `verify` function over, with the first argument set to `map (extract 0) knowledge`.

(From now on, inside `verify`, `knowledge` is a parameter name and refers to the already `extract`ed tuple list.)

(Also, when reading `verify`, note that while the `||` (after the inelegant linebreak to avoid horizontal-scroll on SE) is a normal boolean disjunction between the 'reflexive' and the 'recursive' case, `or` folds that over a list, i.e. checks if any list element is true.)

Now, a relations is obviously correct if it is reflexive. Strictly speaking, no, a `potato` does not *have* a `potato` (and it isn't even one in the sense 'is' is used here, as in 'A Cop is a Cop'), but that's just the termination condition that covers all relationships after walking down the tree (which unlike in the case of real *trees* means 'towards the leafs').

In all other cases, we try to take a tuple from `knowledge` (after we `filter`ed to make sure we 'see' only pairs with the same first element as that we want to check), and go on from where it points to. The list comprehension deals with all possible tuple to continue with and calls `verify` again in each case. A dead end will just have an empty list here and return `false` overall, and so not influence the instance of `verify` it was called by.

---
Tags: code-golf, decision-problem, graph-theory, natural-language
---


title: Across the alphabet

text:
# Question
Title: Across the alphabet
# Across the alphabet

In this challenge, you have trouble remembering the letters of the alphabet. To circumvent this, you go up and down the alphabet, till you get to the letter.

Because you want your code to be portable, you'll be writing it with letter blocks. You have a limited amount of letter blocks because most of them got stolen so you need to make sure your code is as short as possible.

## Examples

Input / Output pairs are separated by a blank line:

```
Ac
ABc

Ad
ABcd

fA
fedCBA

adB
abcdcB

Hello, World!
HGfefghijkllmno, WVUTSrqpopqrqponmlkjihgfed!

```

## Challenge

Your goal is to chain adjacent letters with all the intermediate letters of the alphabet (`A-Za-z`) between them. If capitalization differs, the capitalization should be transformed in the middle. If capitalization cannot be evenly transformed in the middle, it broken up *after* the middle. If a character isn't an alphabetical character, no transformation should be done.

## Winning

This is so shortest code in bytes wins!

**-10% Bonus:** if your code chains digits

# Answer
> 4 votes
# Pyth, 40 bytes

```
+sm?-rdZGhd+hdsrVc2jktr.*rdZm!}kGd.:z2ez

```

Try it online.

# Answer
> 2 votes
# Python 2, ~~303~~ ~~291~~ ~~288~~ ~~282~~ ~~276~~ ~~261~~ 253 bytes

This is a completely different algorithm than Hannes Karppila's, and after lots of golfing, I've managed a substantial improvement in length. I think this algorithm might allow for one of the shortest codes in other languages too, especially languages with do-while loops and built-in signum functions. Suggestions for further improvement welcome. (Something tells me that whole inner loop should be rewritten as a list comprehension.)

```
l=map(ord,list(raw_input()));f=q=1
while q:
 q=0;m=~-f/2;c=m
 while abs(c)<len(l)-1:
  u=c+f;d=(l[u]-96)%32-(l[c]-96)%32
  if chr(l[c]).isalpha()*chr(l[u]).isalpha()*(d*d>1):l[:u-m]+=[l[c]+d/abs(d)];u+=f;q=1
  c=u
 f=-f
print "".join(map(chr,l))

```

# Answer
> 1 votes
# JavaScript (ES6), ~~198~~ ~~197~~ 194 bytes

```
f=s=>(o="",a=u=0,[...s].map(c=>{j=c.toUpperCase();p=j==c;b=j<"A"|j>"Z"?0:j.charCodeAt();for(i=0,m=a<b?b-a:a-b;a&&b&&++i<m;)o+=String.fromCharCode(i*(a<b||-1)+a+32*!(i>m/2?p:u));a=b;u=p;o+=c}),o)

```

## Usage

```
f("Hello, World!")
=> "HGfefghijkllmno, WVUTSrqpopqrqponmlkjihgfed!"

```

## Explanation

```
f=s=>(
  o="",                                   // o = output string
  a=                                      // a = previous character code (or 0 if symbol)
    u=0,                                  // u = 1 if previous character was upper-case
  [...s].map(c=>{                         // iterate through each letter of input

    // Get information about the current character
    j=c.toUpperCase();                    // j = current character in upper-case
    p=j==c;                               // p = current character is upper-case
    b=j<"A"|j>"Z"?0:j.charCodeAt();       // b = current character code (or 0 if symbol)

    // Interpolate characters (unless A or B is a symbol)
    for(i=0,m=a<b?b-a:a-b;a&&b&&++i<m;)   // loop for each character between A and B
      o+=String.fromCharCode(             // add interpolated character to output
        i*(a<b||-1)+a+                    // interpolate character code
          32*!(i>m/2?p:u)                 // apply case of the nearest character
      );

    // Set character A values to B for the next character
    a=b;
    u=p;
    o+=c                                  // add B itself to the output

  }),
  o                                       // return the output
)

```

# Answer
> 1 votes
# JavaScript ES6, 168 (186-10%) ~~176 193~~

**Edit** Modified to get the 10% bonus

Test running the snippet below using an EcmaScript 6 compliant browser (I use FireFox)

```
f=s=>[...s].map(c=>{a=parseInt(c,36),m=(a-q)/(d=a>q?1:-1);for(n=1;m&&(a>9)==(q>9)&&(q+=d)!=a;n+=2)r=q.toString(36),o+=n<m&p<'a'|n>=m&c<'a'?r.toUpperCase():r;p=c,q=a,o+=c},o='',p=q=-f)&&o

// Explained
U=s=>(
  o = '', // initialize output
  p = '', // provious char, initialize to none
  q = NaN, // previous char code, initialize to none
  [...s].map( c => { // for each char
    a = parseInt(c,36), // convert digit/letter to numeric code, case invariant, NaN if invalid
    d = a > q ? 1 : -1, // sign of difference (if not equal)
    m = (a - q) / d; // absolute value of difference or NaN
    if (m && (a>9)==(q>9)) // if current and prev are different and both alpha or both digits
      for( n = 1;
          (q += d) != a; // loop from prev char (not included) to current (not included)
           n += 2)
        r=q.toString(36),
        // add intermediate char to output
        // upcase if: left side & prev is upcase or right side and current is upcase
        o+= n<m&p<'a'|n>=m&c<'a'?r.toUpperCase():r;
    p = c, // copy current to previous
    q = a, // copy current to previous
    o += c // add current char to ouput
  }),
  o
)

// test
console.log=(...x)=>O.innerHTML+=x+'\n'

;['Ac','Ad','fA','adB','04aQ27','Hello World!'].
forEach(x=>console.log(x + ' -> ' + f(x)))
```

```
<pre id=O></pre>
```

# Answer
> 0 votes
# Python 2, 349 bytes

It's way too long, but at least it's first.

```
f=lambda p:ord(p.lower())
u=lambda p:"".join(p).upper()
s=raw_input()
w=s[0]
r=w
for q in s[1:]:
 o=q+w
 if q==w:o=""
 if o.isalpha():
  m=(f(w)<f(q))*2-1
  e=map(chr,range(f(w)+m,f(q)+m,m))
  if o==u(o):e=u(e)
  elif q==u(q):e[len(e)/2:]=u(e[len(e)/2:])
  elif -o.islower()+1:e[:len(e)/2]=u(e[:len(e)/2])
  r+="".join(e)
 else:
  r+=q
 w=q
print r

```

---
Tags: code-golf, string, alphabet
---


title: Make my pseudocode real

text:
# Question
Title: Make my pseudocode real
I've got some Java pseudocode that uses whitespace instead of curly braces, and I want *you* to convert it.

## I/O

Your program should take an input file along with a number designating how many spaces are used to indent a block. Here's an example:

```
$ convert.lang input.p 4
// Convert using 4 spaces as the block delimiter
$ convert.lang input.p 2
// Convert using 2 spaces as the block delimiter

```

It should then convert the result using the specified block delimiter and output the result to stdout.

## The meat of the program

Blocks open with `:` and each line within the block is indented using the block delimiter, like Python code.

```
while(true):
    System.out.println("Test");

```

Each `:` is replaced with a  `{`, and a `}` is appended to the end of the block.

```
while(true) {
    System.out.println("Test");
}

```

## Examples

*Input:*

```
public class Test:
    public static void main(String[] args):
        System.out.println("Java is verbose...");
```

*Output:*

```
$ convert Test.pseudojava 4
public class Test {
    public static void main(String[] args) {
        System.out.println("Java is verbose...");
    }
}
```

*Input:*

```
main():
  printf("Hello World");

```

*Output:*

```
$ convert test.file 2
main() {
  printf("Hello World");
}
```

*Input:*

```
def generic_op(the_stack, func):
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list):
        if b:
            return
        top = b.pop(0)
        while b:
            top = func(top, b.pop(0))
        the_stack.push(top)
    else:
        a = the_stack.pop()
        return func(a, b)
```

*Output:*

```
$ convert code.py 4
def generic_op(the_stack, func){
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list) {
        if b {
            return
        }
        top = b.pop(0)
        while b {
            top = func(top, b.pop(0))
        }
        the_stack.push(top)
    }
    else {
        a = the_stack.pop()
        return func(a, b)
    }
}

```

## Scoring

The code with the least amount of bytes wins!

# Answer
> 5 votes
# Perl, 41 bytes

```
#!perl -p0
1while s/( *).*\K:((
\1 .*)+)/ {\2
\1}/

```

Counting the shebang as two, input is taken from stdin. A command line argument need not be provided. Any valid nesting context can be determined (and matched) without knowing the indentation size.

---

**Regex Break-Down**

```
( *)                   # as many spaces as possible (\1)
    .*                 # as many non-newline characters as possible \
                         (greediness ensures this will always match a full line)
      \K               # keep all that (i.e. look-behind assertion)
        :              # colon at eol (newline must be matched next)
         (
          (
           \n\1        # newline with at least one more space than the first match
                .*     # non-newlines until eol
                  )+   # as many of these lines as possible
                    )  # grouping (\2)

```

---

**Sample Usage**

*in1.dat*

```
public class Test:
    public static void main(String[] args):
        System.out.println("Java is verbose...");

```

*Output*

```
$ perl py2java.pl < in1.dat
public class Test {
    public static void main(String[] args) {
        System.out.println("Java is verbose...");
    }
}

```

---

*in2.dat*

```
main():
  printf("Hello World");

```

*Output*

```
$ perl py2java.pl < in2.dat
main() {
  printf("Hello World");
}

```

---

*in3.dat*

```
def generic_op(the_stack, func):
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list):
        if b:
            return
        top = b.pop(0)
        while b:
            top = func(top, b.pop(0))
        the_stack.push(top)
    else:
        a = the_stack.pop()
        return func(a, b)

```

*Output*

```
$ perl py2java.pl < in3.dat
def generic_op(the_stack, func) {
    # Generic op handling code
    b = the_stack.pop()
    if isinstance(b, list) {
        if b {
            return
        }
        top = b.pop(0)
        while b {
            top = func(top, b.pop(0))
        }
        the_stack.push(top)
    }
    else {
        a = the_stack.pop()
        return func(a, b)
    }
}

```

# Answer
> 2 votes
# Python 3, ~~299~~ 265 bytes

```
import sys;s=int(sys.argv[2]);t="";b=0
for l in open(sys.argv[1]):
 h=l;g=0
 for c in l:
  if c!=" ":break
  g+=1
 if g/s<b:h=" "*g+"}\n"+h;b-=1
 if l.strip().endswith(":"):h=l.split(":")[0];h+=" {";b+=1
 t+=h+"\n"
b-=1
while b>-1:
 t+=" "*(b*s)+"}\n"b-=1
print(t)

```

Boom bam pow.

Algorithm used:

```
//global vars
string total //total modified program
int b //indent buffer

line thru lines: //iterate over every line
  string mline = "" //line to be added to the total

  //calculate the amount of spaces before the line (could be a lot easier)
  int spaces = 0 //total spaces
  c thru line: //go through every character in the line
    if c != " ": //if the current char isn't a space (meaning we went though all of them
        break //break out of iterating through chars
    spaces++ //increment the spaces because we've hit a space (hurr derr)

  if spaces/SPACE_SETTING < b: //if indent count of the current line is less than the indent buffer
    mline = "}\n" + line //add closing bracket to beginning of line
    b-- //decrement buffer

  if line.endswith(":"): //if the line ends with a `:`
    remove : from line
    mline += " {" //append {
    b++ //increment buffer
  total += mline //add modified line to total

print(total)

```

# Answer
> 2 votes
# Ruby, 70

```
x=$_+"
"
1while x.sub! /^(( *).*):
((\2 .*?
)*)/,'\1 {
\3\2}
'
$><<x

```

Adds a trailing newline. Does not need the indent block-size parameter.

Run this with `-n0` (this is really 68+2). Thank you greatly to @primo for saving over a dozen bytes.

---
Tags: code-golf, string
---


title: The Interview: The Front Nine

text:
# Question
Title: The Interview: The Front Nine
# The Interview: The Front Nine

<sup>*This is the first of a series of challenges inspired by programming job interview questions.*</sup>

You walk into the office where your potential future boss sits. "Come on in and sit down", he says. You nervously sit down, making sure your snappy yet professional attire is free of wrinkles. He asks you many questions, about your education, previous work experiences, and so on. You answer them mostly honestly, adding a little embellishment here and there to make yourself sound better. He leans forward and begins to speak again.

"Have you ever heard of code golfing?" Why, yes, you love to golf code, and do it frequently in your free time. "Great. The last part of the interview is a technical examination. You will be tasked with writing code to solve a series of problems..." He hands you a sheet of paper. You quickly glance over it. Easy peasy. Now why did he ask about code golfing?

"You will be graded based on the total size of your solutions to these problems. If you can score lower than all the other candidates, the job is yours." Oh. "Like golf, there are 18 problems, broken up into two sets of 9. Feel free to use any language you like to solve them; we have compilers and interpreters for every language you've heard of, and certainly a few that you haven't. Good luck!"

## The Tasks

### Task 1: Multiplication Table

Given a number `n` as input, output a multiplication table for positive integers in the range `[1, n]`. `n` will be in the range `[1, 12]`. All numbers should be left-aligned in the table. Use the character `x` for the top-left corner.

Examples:

```
n=4
x   1   2   3   4
1   1   2   3   4
2   2   4   6   8
3   3   6   9   12
4   4   8   12  16

n=10
x   1   2   3   4   5   6   7   8   9   10
1   1   2   3   4   5   6   7   8   9   10
2   2   4   6   8   10  12  14  16  18  20
3   3   6   9   12  15  18  21  24  27  30
4   4   8   12  16  20  24  28  32  36  40
5   5   10  15  20  25  30  35  40  45  50
6   6   12  18  24  30  36  42  48  54  60
7   7   14  21  28  35  42  49  56  63  70
8   8   16  24  32  40  48  56  64  72  80
9   9   18  27  36  45  54  63  72  81  90
10  10  20  30  40  50  60  70  80  90  100

```

### Task 2: Ordinal RMS

Given a string of ASCII characters, output the root-mean-square average of their ASCII ordinals. The string will never contain a NULL byte (ordinal 0).

Examples:

```
Input: The Interview: The Front Nine
Output: 95.08290393488019

Input: `1234567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./
Output: 91.38101204135423

```

### Task 3: Projectile Motion

Given the initial velocity and angle with the horizon of a projectile fired from ground level, output the horizontal distance it will travel before landing. The initial velocity will be given in meters per second, the angle will be given in degrees, and the distance shall in meters. Assume Earth gravity (`g=9.81 m/s/s`), and ignore relativistic effects. For the sake of this problem, you may assume the Earth is flat (you will not need to consider the curvature of the Earth when making your calculations). The given angle will be in the range `[0, 90]`. Your answer should be accurate to at least two decimal places (rounding is allowed).

Examples:

```
velocity=50, angle=45
Result: 254.84 (rounded)

velocity=10, angle=60
Result: 8.82798576742547

```

### Task 4: etaoin shrdlu

Given a string of non-null printable ASCII characters (ordinals in the range `[32,127]`), output the string, with its characters sorted by their frequencies in descending order. In the case of a tie, order by ASCII ordinal, ascending.

Examples:

```
Input: "Hello, World!"
Output: "llloo !,HWder"

Input: "Programming Puzzles and Code Golf"
Output: "    oooPPaaddeeggllmmnnrrzzCGfisu"

```

### Task 5: Fibonacci Index

Given a number, determine if it is a Fibonacci number, and if it is, output its index (starting from 1) in the sequence. If it is not a Fibonacci number, output 0. In the case of 1, which is in the sequence twice, output the earliest occurrence (index 1).

Examples:

```
Input: 1
Output: 1

Input: 144
Output: 12

Input: 4
Output: 0

```

### Task 6: Anagrams

Given three strings of lowercase English letters (`[a-z]`), output a string that uses all the letters in the first string, begins with the second string, and ends with the third string. If such a string cannot be constructed, output an empty string. The input strings will always be at least one letter long. The "middle" of the output string (between the prefix and postfix string) may be empty, if the prefix and postfix strings together use all of the letters in the source string.

Examples:

```
Input: geobits bi es
Possible output: bigtoes

Input: mariatidaltug digital trauma
Output: digitaltrauma

Input: mego go lf
Output: (empty string)

```

### Task 7: Filling In The Blanks

Given a list of strings and a fill character, output the result of padding all of the strings to the length of the longest string with the fill character, sorted in ascending order by the original lengths of the strings, preserving the original order in the case of a tie. You should be able to handle lists of any finite length, containing strings of any finite length, bounded only by memory constraints.

Examples:

```
Input: ["hello","world","this","is","a","test"], 'x'
Output: ["axxxx","isxxx","thisx","testx","hello","world"]

Input: ["I'm","a","lumberjack","and","I'm","okay"], '!'
Output: ["a!!!!!!!!!","I'm!!!!!!!","and!!!!!!!","I'm!!!!!!!","okay!!!!!!","lumberjack"]

```

### Task 8: Making Change

Given a number in the range `[0.01,0.99]`, output the number of each of the 4 standard US coins that should be used to represent this value such that the total number of coins is minimized. The input will always have exactly 2 places behind the decimal.

Coin value reference:

`Penny: 0.01, Nickel: 0.05, Dime: 0.10, Quarter: 0.25`

Examples:

```
Input: 0.75
Output: [0,0,0,3]

Input: 0.23
Output: 3 pennies, 0 nickels, 2 dimes, 0 quarters

```

### Task 9: Merging Ranges

Given a finite list of 2-tuples containing integers that represent ranges, output the result of merging all overlapping or adjacent ranges. All ranges will be at least of length 1, and the starting value will always be less than the ending value. The order of the output does not matter.

Examples:

```
Input: (2,3), (4,5), (6,9), (0,7)
Output: (0,9)

Input: (-3,4), (2,5), (-10,-4)
Output (-10,-4), (-3,5)

Input: (2,3), (5,6), (6,8)
Output: (5,8), (2,3)

```

---

## Rules

* This is , so shortest answer (in bytes) wins.
* Your score will be the sum of the byte counts for all of your solutions.
* Standard loopholes are forbidden.
* Input and output may be performed in whatever manner is considered standard for your language.
* You may write full programs or functions for each challenge, and may interchange between the two across challenges.
* You must use the same language for all the challenges. If version differences are significant enough for them to be usually considered separate entries in challenges, you must use the same version throughout. For example, if you use Python, you must use either Python 2 or Python 3 for all challenges.
* You must solve all of the challenges. Answers that only solve some of the challenges will be considered non-competitive.
* You may use language builtins or standard libraries.

### Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 63014; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 45941; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "//api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "//api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(42), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
```

# Answer
> 7 votes
# Pyth, ~~155~~ ~~153~~ ~~149~~ ~~142~~ ~~141~~ ~~131~~ 130 bytes

*4 bytes thanks to @FryAmTheEggman*

*1, 5 and 4 bytes thanks to @Jakube*

1. 24 bytes: `J+1SQp\xtjmsm.[`*dk\ 4JJ`

Construct the multiplication table from the list `[1, 1, 2, 3, ...]`, which is `+1SQ`, then print a `x` and remove its first character.

2. 10 bytes: `@.Om^Cd2z2`

Straightforward.

3. 18 bytes: `c*.t.tyvw7Z*QQ9.81`

Uses the formula `sin(2 theta) * v^2/a`, where `theta` is the angle, `v` is the initial velocity and `a` is `9.81`

4. 7 bytes: `o_/zNSz`

Straightforward.

5. 15 bytes: `hxeM.u,eNsNQU2Q`

Generate fibonacci pairs, find the index of the input in them, add one.

6. 14 bytes: `IqSzSJj.-zsQQJ`

Use bagwise subtraction to remove the prefix and suffix from the word, then put the remainder of the word in the middle. If the result of this is not a permutation of the input, don't print it.

7. 8 bytes: `C.tolNQz`

Sort by length. Filled transpose. Transpose again.

8. 18 bytes: `Jsttz/L~%Jd[25T5 1`

Output coin counts are in the order `[quarters, dimes, nickels, pennies]`.

Remove first 2 characters of input and cast to int to get cents. Save to `J`. For each number `d` in the list `[25, 10, 5, 1]`, post-assign `J%d` to `J`, then generate the value `/Jd` with the original value of `J`. Print.

9. 16 bytes: `C-M.p,JS{srMQhMJ`

Turn the tuples into ranges, combine into one list, deduplicate and sort. Save this to `J`. Form `J, hMJ` and `hMJ, J`, where `hMJ` is `J` with every element increased by 1. Perform subtraction in both cases. The former is the lower ends of the ranges, the latter is the higher ends. Transpose them into pairs and print.

# Answer
> 8 votes
# CJam, 162

1. 25 bytes`qi),0Xt_ff{*s4Se]}N*s0'xt`
2. 12 bytes`q_:i:mh\,mq/` (© Dennis)
3. 18 bytes`q~P*90/ms\_**9.81/`
4. 12 bytes`q$e`{0=~}$e~` (© Dennis)
5. 16 bytes`1_{_2$+}99*]qi#)`
6. 22 bytes`qS/(1+1$s{1$#Lt}/)@@**`
7. 18 bytes`q~{,}$_z,f{W$e]}p;`
8. 16 bytes`q2>i25A5]:md]W%p`
9. 23 bytes`q~${_0=2$1=>{+$3%}|}*]p`

Dennis agreed to join forces :)

# Answer
> 5 votes
# CJam, 223 bytes

### Task 1, 35 bytes

```
ri_)_,0Xt2m*::*0'xt:s@s,2+f{Se]}/N*

```

Try it online.

### Task 2, 12 bytes

```
q_:i:mh\,mq/

```

Try it online.

### Task 3, 27 bytes

```
rd180/P*_mc\ms]rdf*~4.905/*

```

Try it online.

### Task 4, 12 bytes

```
q$e`{0=~}$e~

```

Try it online.

### Task 5, 17 bytes

```
XXri:R{_2$+}*]R#)

```

Try it online.

### Task 6, 25 bytes

```
re!_rf#:!.*r:S;{N+SN+#)}=

```

Try it online.

### Task 7, 19 bytes

```
{:C;{,}$_W=,f{Ce]}}

```

Try it online.

### Task 8, 33 bytes

```
A4m*{:+}$r2>i:R;{[X5A25].*:+R=}=p

```

Try it online.

### Task 9, 43 bytes

```
{{~1$-,f+}%:|$__,(%a\2ew{:-W<},+e_$2/2,f.+}

```

Try it online.

# Answer
> 3 votes
## Haskell, 650 bytes

Task 1, 88 bytes:

```
f n="x   "++unlines(map(take 4.(++"   ").show=<<)$[1..n]:map(\a->a:map(a*)[1..n])[1..n])

```

Task 2, 76 bytes:

```
g s=sqrt(sum(map(fromIntegral.(^2).fromEnum)s)/sum(s>>[1]))

```

Task 3, 28 bytes

```
v?a=v*v/9.81*sin(2*a*pi/180)

```

Task 4, 60 bytes:

```
import Data.List
i x=concat$sortOn((0-).length)$group$sort x

```

Task 5, 64 bytes

```
j=(%zip[0..]z);x%((i,h):t)|x<h=0|x==h=i|1<2=x%t;z=scanl(+)0(1:z)

```

Task 6, 93 bytes

```
import Data.List
k a b c|q b a&&q c a=b++((a\\b)\\c)++c|1<2="";q=(.sort).isSubsequenceOf.sort

```

Task 7, 81 bytes

```
import Data.List
s!f=map(take(maximum$map r s).(++cycle[f]))(sortOn r s);r=length

```

Task 8, 73 bytes

```
m x=floor(x*100)#[25,10,5,1];x#[]=[];x#(h:t)|(d,m)<-divMod x h=(m#t)++[d]

```

Task 9, 87 bytes (a shameless copy of @MtnViewMark's answer from a similar challenge)

```
n i=foldr(&)[]i;p@(a,b)&(q@(c,d):r)|b<c=p:q&r|a>d=q:p&r|1<3=(min a c,max b d)&r;p&_=[p]

```

# Answer
> 2 votes
# Mathematica 10.3, 465 bytes

All of these are anonymous functions. Also, thanks to Martin for help golfing, since I'm a noob at Mathematica.

### Task 1, 69 bytes

```
Grid@Join[{Join[{"x"},r=Range@#]},Flatten/@({r,Outer[1##&,r,r]}\[Transpose])]&

```

`\[Transpose]` is the 3 byte "transpose" symbol.

### Task 2, 13 bytes

```
Mean[#^2]^.5&

```

or

```
√Mean[#^2]&

```

(√ is 3 bytes). The `RootMeanSquare` built-in isn't quite short enough...

### Task 3, 18 bytes

```
Sin[2#2°]#/9.81#&

```

### Task 4, 57 bytes

```
""<>SortBy[c=Characters@#,{-c~Count~#&,ToCharacterCode}]&

```

### Task 5, 33 bytes

```
Tr@Position[Fibonacci@Range@#,#]&

```

or

```
Tr[Fibonacci@Range@#~Position~#]&

```

or

```
Tr[Fibonacci~Array~#~Position~#]&

```

### Task 6, 178 bytes ~~(currently has a bug)~~

```
({s,a,b}=Characters@{##};q=If[#2~SubsetQ~#,List@@(Plus@@#-Plus@@#2),{}]&;i=If[#!={},##]&;x=i[q[s,a],{}];y=If[x!={},i[q[x,b],{},Null],Null];Echo[If[y!=Null,""<>Join@{a,y,b},""]])&

```

Less golfed:

```
({s,a,b}=Characters@{##};
q=If[#2~SubsetQ~#,List@@(Plus@@#-Plus@@#2),{}]&;
i=If[#!={},##]&;
x=i[q[s,a],{}];
y=If[x!={},i[q[x,b],{},Null],Null];
Echo[If[y!=Null,""<>Join@{a,y,b},""]])&

```

String manipulation is horrid...

### Task 7, 39 bytes

```
#~SortBy~StringLength~StringPadRight~#1

```

### Task 8, 46 bytes

```
FrobeniusSolve[{1,5,10,25},100#]~MinimalBy~Tr&

```

or

```
{.1,.5,.10,.25}~FrobeniusSolve~#~MinimalBy~Tr&

```

### Task 9, 12 bytes

```
Interval@##&

```

Intervals passed to the constructor are automatically union-ed. Beat that.

---
Tags: code-golf, math, string, physics, multiple-holes
---


title: Remove the hyphenation

text:
# Question
Title: Remove the hyphenation
Time for a new challenge! It’s a common problem when copy-pasting between various document formats: hyphenation. While it reduces the raggedness of a left-aligned layout or evens spacing in a justified layout, it’s a complete pain when your PDF is not properly constructed and retains the hyphens in the layout, making your copied text difficult to edit or reflow.

Luckily, if we are to believe the countless self-help books out there, nothing is a problem if you see it as a challenge. I believe these self-help books are without exception referring to PPCG, where any problem will be solved if presented as a challenge. Your task is to remove offending hyphenation and linebreaks from a text, so that it is ready to paste in any text editor.

# Problem description

You will write a program or function that removes hyphenation and line-breaks where applicable. The **input** will be a string on `stdin` (or closest alternative) or as a function input. The **output** (on `stdout` or closest alternative or function output) will be the 'corrected' text. This text should be **directly** copy-pastable. This means that leading or trailing output is OK, but additional output halfway your corrected text (e.g., leading spaces on every line) is **not**.

The most basic case is the following (note: no trailing spaces)

```
Lorem ipsum dolor sit amet, con-
sectetur adipiscing elit. Morbi
lacinia nisi sed mauris rhoncus.

```

The offending hyphen and linebreaks should be removed, to obtain

```
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Morbi lacinia nisi sed mauris rhoncus.

```

However, a few exceptions should be observed.

* Double newlines indicate a paragraph break, and should be retained.
* Proper nouns and names are never broken across two lines, unless they already contain a hyphen (e.g. Navier-Stokes equations). The line-break should be removed, but the hyphen retained. These cases can be identified by having only the first letter capitalized.
* Sometimes, a hyphen indicates a word group (e.g. nineteenth- and twentieth century). When this happens across two lines, this is indicated with a leading space on the next line.

An example: *(views expressed in this example are fictional and do not necessarily represent the view of the author; opponents of the Runge-Kutta-Fehlberg method are equally welcome to participate in this challenge)*

```
Differential equations can
be solved with the Runge-Kutta-
Fehlberg method.

Developed in the nineteenth-
 or twentieth century, this
method is completely FANTAS-
TIC.

```

will become

```
Differential equations can be solved with the Runge-Kutta-Fehlberg method.

Developed in the nineteenth- or twentieth century, this method is completely FANTASTIC.

```

The linebreaks can be either the `\n` or `\r\n` ASCII code-point depending on your preference, and the hyphen is a simple ASCII `-` (minus sign). UTF-8 support is not required. This challenge is , so shortest code wins.

# Answer
# Retina, 58 bytes

```
(?<!\n)\n(?!\n)
<space>
- (?! |[A-Z][a-z])| (?= )|(?<=-) (?=[A-Z])
<empty>

```

`<space>` represents a single space on its own line and `<empty>` represents an empty trailing line. For counting purposes, each line goes into a separate file and the `\n` are replaced with actual linefeed characters. For convenience you can put all of the above in a single file though and run it with the `-s` flag.

I'm pretty sure there's a shorter way to do this, so I'll wait with an explanation until I'm done golfing.
> 9 votes

# Answer
# GNU Sed, 68

Score includes +2 for `-zr` options passed to `sed`.

```
s/\n\n/:/g
s/-\n([A-Z][a-z])/-\1/g
s/-\n /- /g
s/-\n//g
y/\n:/ \n/

```

Assumes that the input stream doesn't contain any `:` characters. If this is not acceptable, then the `:`'s in the code may be all replaced with some other non-printable ASCII character, e.g. 0x7 BEL.
> 2 votes

# Answer
# TeaScript, 76 bytes

```
xB(`([A-Z][a-z]+-)
(\\S)`,b="$1$2",`(\\S)-
(\\S)`,b,`(\\S-?)
 ?(.)`,"$1 $2")

```

Very "brute force" method.

Try it online
> 2 votes

---
Tags: code-golf, typography
---


title: Set Theoretic Arithmetic (+ and *)

text:
# Question
Title: Set Theoretic Arithmetic (+ and *)
# Set Theoretic Arithmetic

## Premise

There have been a couple challenges already that involve multiplying without the multiplication operator ( here and here ) and this challenge is in the same vein (most similar to the second link).

This challenge, unlike those previous, will use a set theoretic definition of the natural numbers (***N***):

and

for example,

and so on.

## The Challenge

Our goal is to use set operations (see below), to add and multiply natural numbers. For this purpose, **all entries will be in the same 'set language' whose interpreter is below**. This will provide consistency as well as easier scoring.

This interpreter allows you to manipulate natural numbers as sets. Your task will be to write two program bodies (see below), one of which adds natural numbers, the other of which multiplies them.

## Preliminary Notes on Sets

Sets follow the usual mathematical structure. Here are some important points:

* Sets are not ordered.
* No set contains itself
* Elements are either in a set or not, this is boolean. Therefore set elements cannot have multiplicities (i.e. an element cannot be in a set multiple times.)

## Interpreter and specifics

A 'program' for this challenge is written in 'set language' and consists of two parts: a header and a body.

### Header

The header is very simple. It tells the interpreter what program you are solving. The header is the opening line of the program. It begins with either the `+` or `*` character, followed by two integers, space delimited. For example:

```
+ 3 5

```

or

```
* 19 2

```

are valid headers. The first indicates that you are trying to solve `3+5`, meaning that your answer should be `8`. The second is similar except with multiplication.

### Body

The body is where your actual instructions to the interpreter are. This is what truly constitutes your "addition" or "multiplication" program. Your answer will have consist of two program bodies, one for each task. You will then change the headers to actually carry out the test cases.

### Syntax and Instructions

Instructions consist of a command followed by zero or more parameters. For the purposes of the following demonstrations, any alphabet character is the name of a variable. Recall that all variables are sets. `label` is the name of a label (labels are words followed by semicolons (i.e. `main_loop:`), `int` is an integer. The following are the valid instructions:

Flow Control: 1. `jump label` jump unconditionally to the label. A label is a 'word' followed by a semicolon: e.g. `main_loop:` is a label.
2. `je A label` jump to label if A is empty
3. `jne A label` jump to label if A is non-empty
4. `jic A B label` jump to label if A contains B
5. `jidc A B label` jump to label if A does not contain B

Variable Assignment 6. `assign A B` or `assign A int`  or
where `set(int)` is the set representation of `int`

Set Ops 7. `union A B C`
8. `intersect A B C`
9. `difference A B C`
10. `add A B`
11. `remove A B`

Debugging 12. `print A` prints the true value of A, where {} is the empty set
13. `printi variable` prints integer representation of A, if it exists, otherwise outputs error.

Comments 14. `;` The semicolon indicates that the rest of the line is a comment and will be ignored by the interpreter

### Further Info

At program start, there are three pre-existing variables. They are **`set1`, `set2`** and **`ANSWER`**. `set1` takes the value of the first header parameter. `set2` takes the value of the second. `ANSWER` is initially the empty set. Upon program completion, the interpreter checks if `ANSWER` is the integer representation of the answer to the arithmetic problem defined in the header. If it is, it indicates this with a message to stdout.

The interpreter also displays the number of operations used. Every instruction is one operation. Initiating a label also costs one operation (Labels can only be initiated once).

You may have a maximum of 20 variables (including the 3 predefined variables) and 20 labels.

### Interpreter code

IMPORTANT NOTES ON THIS INTERPRETER

Things are very slow when using large numbers (\>30) in this interpreter. I will outline the reasons for this.

* The structures of sets is such that in increasing by one natural number, you effectively double the size of the set structure. The *n*th natural number has *2^n* empty sets within it (by this I mean that if you look *n* as a tree, there are *n* empty sets. Note only empty sets can be leaves.) This means that dealing with 30 is significantly more costly than dealing with 20 or 10 (you're looking at 2^10 vs 2^20 vs 2^30).
* Equality checks are recursive. Since sets are allegedly unordered, this seemed the natural way to tackle this.
* There are two memory leaks that I couldn't figure out how to fix. I'm bad at C/C++, sorry. Since we're dealing with small numbers only, and allocated memory is freed at program end, this shouldn't really be that much of an issue. (Before anyone says anything, yes I know about `std::vector`; I was doing this as a learning exercise. If you do know how to fix it, please let me know and I will make the edits, otherwise, since it works, I will leave it as is.)

Also, notice the include path to `set.h` in the `interpreter.cpp` file. Without further ado, the source code (C++):

### set.h

```
using namespace std;

//MEMORY LEAK IN THE ADD_SELF METHOD
class set {

    private:
        long m_size;
        set* m_elements;
        bool m_initialized;
        long m_value;

    public:
        set() {

            m_size =0;
            m_initialized = false;
            m_value=0;
        }

        ~set() {
            if(m_initialized) {
                //delete[] m_elements;
            }
        }

        void init() {
            if(!m_initialized) {
                m_elements = new set[0];

                m_initialized = true;
            }
        }

        void uninit() {
            if(m_initialized) {
                //delete[] m_elements;
            }
        }

        long size() {
            return m_size;
        }

        set* elements() {
            return m_elements;
        }

        bool is_empty() {
            if(m_size ==0) {return true;}
            else {return false;}
        }

        bool is_eq(set otherset) {
            if( (*this).size() != otherset.size() ) {
                return false;
            }
            else if ( (*this).size()==0 && otherset.size()==0 ) {
                return true;
            }
            else {
                for(int i=0;i<m_size;i++) {
                    bool matched = false;
                    for(int j=0;j<otherset.size();j++) {

                        matched = (*(m_elements+i)).is_eq( *(otherset.elements()+j) );
                        if( matched) {
                            break;
                        }
                    }
                    if(!matched) {
                        return false;
                    }
                }
                return true;
            }
        }

        bool contains(set set1) {
            for(int i=0;i<m_size;i++) {
                if( (*(m_elements+i)).is_eq(set1) ) {
                    return true;
                }
            }
            return false;
        }

        void add(set element) {
            (*this).init();

            bool alreadythere = false;
            for(int i=0;i<m_size;i++) {
                if( (*(m_elements+i)).is_eq(element) ) {
                    alreadythere=true;
                }
            }
            if(!alreadythere) {
                set *temp = new set[m_size+1];
                for(int i=0; i<m_size; i++) {
                    *(temp+i)= *(m_elements+i);
                }
                *(temp+m_size)=element;

                m_size++;
                delete[] m_elements;
                m_elements = new set[m_size];

                for(int i=0;i<m_size;i++) {
                    *(m_elements+i) = *(temp+i);
                }
                delete[] temp;
            }
        }

        void add_self() {

            set temp_set;
            for(int i=0;i<m_size;i++) {
                temp_set.add( *(m_elements+i) );
            }
            (*this).add(temp_set);
            temp_set.uninit();
        }

        void remove(set set1) {
            (*this).init();
            for(int i=0;i<m_size;i++) {
                if(  (*(m_elements+i)).is_eq(set1) ) {

                    set* temp = new set[m_size-1];
                    for(int j=0;j<m_size;j++) {

                        if(j<i) {
                            *(temp+j)=*(m_elements+j);
                        }
                        else if(j>i) {
                            *(temp+j-1)=*(m_elements+j);
                        }
                    }
                    delete[] m_elements;
                    m_size--;
                    m_elements = new set[m_size];
                    for(int j=0;j<m_size;j++) {
                        *(m_elements+j)= *(temp+j);
                    }
                    delete[] temp;
                    break;
                }
            }
        }

        void join(set set1) {
            for(int i=0;i<set1.size();i++) {
                (*this).add( *(set1.elements()+i) );
            }
        }

        void diff(set set1) {
            for(int i=0;i<set1.size();i++) {
                (*this).remove( *(set1.elements()+i) );
            }
        }

        void intersect(set set1) {
             for(int i=0;i<m_size;i++) {

                bool keep = false;
                 for(int j=0;j<set1.size();j++) {
                     if(  (*(m_elements+i)).is_eq( *(set1.elements()+j) ) ) {
                         keep = true;
                         break;
                     }
                 }
                 if(!keep) {
                    (*this).remove( *(m_elements+i) );
                 }
             }
         }

        void natural(long number) {
            //////////////////////////
            //MEMORY LEAK?
            //delete[] m_elements;
            /////////////////////////
            m_size = 0;
            m_elements = new set[m_size];

            for(long i=1;i<=number;i++) {
                (*this).add_self();
            }
            m_value = number;
        }

        void disp() {
            if( m_size==0) {cout<<"{}";}
            else {
                cout<<"{";
                for(int i=0; i<m_size; i++) {
                    (*(m_elements+i)).disp();
                    if(i<m_size-1) {cout<<", ";}
                    //else{cout<<" ";}
                }
                cout<<"}";
            }
        }

        long value() {
            return m_value;
        }

};
const set EMPTY_SET;

```

### interpreter.cpp

```
#include<fstream>
#include<iostream>
#include<string>
#include<assert.h>
#include<cmath>
#include "headers/set.h"
using namespace std;
string labels[20];
int jump_points[20];
int label_index=0;
const int max_var = 20;
set* set_ptrs[max_var];
string set_names[max_var];
long OPERATIONS = 0;

void assign_var(string name, set other_set) {
    static int index = 0;
    bool exists = false;
    int i = 0;
    while(i<index) {
        if(name==set_names[i]) {
            exists = true;
            break;
        }
        i++;
    }
    if(exists && index<max_var) {
        *(set_ptrs[i]) = other_set;
    }
    else if(!exists && index<max_var) {
        set_ptrs[index] = new set;
        *(set_ptrs[index]) = other_set;
        set_names[index] = name;
        index++;
    }
}

int getJumpPoint(string str) {
    for(int i=0;i<label_index;i++) {
        //cout<<labels[i]<<"\n";
        if(labels[i]==str) {
            //cout<<jump_points[i];
            return jump_points[i];
        }
    }
    cerr<<"Invalid Label Name: '"<<str<<"'\n";
    //assert(0);
    return -1;
}

long strToLong(string str) {
    long j=str.size()-1;
    long value = 0;
    for(long i=0;i<str.size();i++) {
        long x = str[i]-48;
        assert(x>=0 && x<=9);  // Crash if there was a non digit character
        value+=x*floor( pow(10,j) );
        j--;
    }
    return value;
}

long getValue(string str) {
    for(int i=0;i<max_var;i++) {
        if(set_names[i]==str) {
            set set1;
            set1.natural( (*(set_ptrs[i])).size() );
            if( set1.is_eq( *(set_ptrs[i]) )   ) {
                return (*(set_ptrs[i])).size();
            }
            else {
                cerr<<"That is not a valid integer construction";
                return 0;
            }
        }
    }
    return strToLong(str);
}

int main(int argc, char** argv){
    if(argc<2){std::cerr<<"No input file given"; return 1;}
    ifstream inf(argv[1]);
    if(!inf){std::cerr<<"File open failed";return 1;}
    assign_var("ANSWER", EMPTY_SET);
    int answer;
    string str;
    inf>>str;
    if(str=="*") {
        inf>>str;
        long a = strToLong(str);
        inf>>str;
        long b = strToLong(str);
        answer = a*b;
        set set1; set set2;
        set1.natural(a); set2.natural(b);
        assign_var("set1", set1);
        assign_var("set2",set2);
        //cout<<answer;
    }
    else if(str=="+") {
        inf>>str;
        long a = strToLong(str);
        inf>>str;
        long b = strToLong(str);
        answer = a+b;
        set set1; set set2;
        set1.natural(a); set2.natural(b);
        assign_var("set1", set1);
        assign_var("set2",set2);
        //cout<<answer;
    }
    else{
         cerr<<"file must start with '+' or '*'";
        return 1;
    }

    // parse for labels
    while(inf) {
        if(inf) {
            inf>>str;
            if(str[str.size()-1]==':') {
                str.erase(str.size()-1);
                labels[label_index] = str;
                jump_points[label_index] = inf.tellg();
                //cout<<str<<": "<<jump_points[label_index]<<"\n";
                label_index++;
                OPERATIONS++;
            }
        }
    }

    inf.clear();
    inf.seekg(0,ios::beg);
    // parse for everything else

    while(inf) {
        if(inf) {
            inf>>str;

            if(str==";") {
                getline(inf, str,'\n');
            }

            // jump label
            if(str=="jump") {
                inf>>str;
                inf.seekg( getJumpPoint(str),ios::beg);
                OPERATIONS++;
            }

            // je set label
            if(str=="je") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str) {
                        if( (*(set_ptrs[i])).is_eq(EMPTY_SET) ) {
                            inf>>str;
                            inf.seekg( getJumpPoint(str),ios::beg);
                            OPERATIONS++;
                        }
                        break;
                    }
                }
            }

            // jne set label
            if(str=="jne") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str) {
                        if(! (*(set_ptrs[i])).is_eq(EMPTY_SET) ) {
                            inf>>str;
                            inf.seekg( getJumpPoint(str),ios::beg);
                            OPERATIONS++;
                        }
                        break;
                    }
                }
            }

            // jic set1 set2 label
            // jump if set1 contains set2
            if(str=="jic") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set set2;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str ) {
                        set1 = *(set_ptrs[i]);
                    }
                    if(set_names[i]==str2) {
                        set2 = *(set_ptrs[i]);
                    }
                }
                if( set1.contains(set2) ) {
                    inf>>str;
                    inf.seekg( getJumpPoint(str),ios::beg);
                    OPERATIONS++;
                }
                else {inf>>str;}
            }

            // jidc set1 set2 label
            // jump if set1 doesn't contain set2
            if(str=="jidc") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set set2;
                for(int i=0;i<max_var;i++) {
                    if( set_names[i]==str ) {
                        set1 = *(set_ptrs[i]);
                    }
                    if(set_names[i]==str2) {
                        set2 = *(set_ptrs[i]);
                    }
                }
                if( !set1.contains(set2) ) {
                    inf>>str;
                    inf.seekg( getJumpPoint(str),ios::beg);
                    OPERATIONS++;
                }
                else {inf>>str;}
            }

            // assign variable set/int
            if(str=="assign") {
                inf>>str;
                string str2;
                inf>>str2;
                set set1;
                set1.natural( getValue(str2) );
                assign_var(str,set1);
                OPERATIONS++;

            }

            // union set1 set2 set3
            // set1 = set2 u set3
            if(str=="union") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]);
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.join(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;

            }

            // intersect set1 set2 set3
            // set1 = set2^set3
            if(str == "intersect") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]);
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.intersect(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;
            }

            // difference set1 set2 set3
            // set1 = set2\set3
            if(str == "difference") {
                inf>>str;
                int i=0;
                while(i<max_var) {
                    if( set_names[i] == str ) {
                        break;
                    }
                    i++;
                }

                set set1;
                set set2;
                string str1;
                inf>>str1;
                string str2;
                inf>>str2;
                for(int j=0;j<max_var;j++) {
                    if( str1 == set_names[j] ) {
                        set1= *(set_ptrs[j]);
                    }
                    if( str2 == set_names[j] ) {
                        set2= *(set_ptrs[j]);
                    }
                }
                set1.diff(set2);
                if(i==max_var) {
                    assign_var(str,set1);
                }
                else {
                    set_names[i]= str;
                    set_ptrs[i] = new set;
                    *(set_ptrs[i]) = set1;
                }
                OPERATIONS++;
            }

            // add set1 set2
            // put set2 in set 1
            if(str=="add") {
                inf>>str;
                int i = 0; int j =0;
                while(i<max_var) {
                    if(set_names[i]==str) {
                        break;
                    }
                    i++;
                }
                inf>>str;
                while(j<max_var) {
                    if(set_names[j]==str) {
                    break;
                    }
                    j++;
                }
                set set2 = *(set_ptrs[j]);
                if( ! (*(set_ptrs[i])).is_eq(set2) ){
                    (*(set_ptrs[i])).add(set2);
                }
                else {
                    (*(set_ptrs[i])).add_self();
                }
                OPERATIONS++;
            }

            // remove set1 set2
            // remove set2 from set1
            if(str=="remove") {
                inf>>str;
                int i = 0; int j =0;
                while(i<max_var) {
                    if(set_names[i]==str) {
                        break;
                    }
                    i++;
                }
                inf>>str;
                while(j<max_var) {
                    if(set_names[j]==str) {
                    break;
                    }
                    j++;
                }
                set set2 = *(set_ptrs[j]);
                (*(set_ptrs[i])).remove(set2);
                OPERATIONS++;
            }

            // print set
            // prints true representation of set
            if(str=="print") {
                inf>>str;
                for(int i=0;i<max_var;i++) {
                    if(set_names[i]==str) {
                        (*(set_ptrs[i])).disp();
                    }
                }
                cout<<"\n";
            }

            // printi set
            // prints integer representation of set, if exists.
            if(str=="printi") {
                inf>>str;
                cout<<getValue(str);
                cout<<"\n";
            }
        }
    }

    cout<<"You used "<<OPERATIONS<<" operations\n";
    set testset;
    testset.natural(answer);
    switch( testset.is_eq( *(set_ptrs[0]) ) ) {
        case 1:
            cout<<"Your answer is correct, the set 'ANSWER' is equivalent "<<answer<<".\n";
            break;
        case 0:
            cout<<"Your answer is incorrect\n";
    }
   // cout<<"\n";
    return 0;
}

```

## Winning condition

**You are two write two program *BODIES***, one of which multiplies the numbers in the headers, the other of which adds the numbers in the headers.

This is a challenge. What is fastest will be determined by the number of operations used to solve two test cases for each program. The test cases are the following headers lines:

For addition:

```
+ 15 12

```

and

```
+ 12 15

```

and for multiplication

```
* 4 5

```

and

```
* 5 4

```

A score for each case is the number of operations used (the interpreter will indicate this number upon program completion). The total score is the sum of the scores for each test case.

See my example entry for an example of a valid entry.

A winning submission satisfies the following:

1. contains two program bodies, one which multiplies and one which adds
2. has the lowest total score (sum of scores in test cases)
3. Given sufficient time and memory, works for any integer that could be handled by the interpreter (~2^31)
4. Displays no errors when run
5. Does not use debugging commands
6. Does not exploit flaws in the interpreter. This means that your actual program should be valid as pseudo-code as well as an interpretable program in 'set language'.
7. Does not exploit standard loopholes (this means no hardcoding test cases.)

Please see my example for reference implementation and example usage of the language.

# Answer
# Example Answer, 1323 Operations

*Note that this is an example, not a real entry.*

**Addition Body**

Note that this body will not run without a header.

Comments are not necessary in an actual answer, but are there to help teach the basics of the language.

```
assign ANSWER set2                  ; ANSWER = set2
main:                               ; create label 'main'
    add ANSWER ANSWER               ; Answer union {Answer}, i.e. ANSWER++
    assign looper1 0
    assign looper2 0
    jump dec
    continue:
        intersect set1 set1 looper2 ; set1 = set1 intersect looper2, i.e. set1 = min(set1,looper2)
        jne set1 main
        jump end
dec:
    add looper1 looper1             ; looper1++
    jidc set1 looper1 continue      ; jump if looper >= set1
    add looper2 looper2             ; looper2++
    jump dec
end:

```

For test case

```
+ 15 12

```

uses `440 operations` and for test case

```
+ 12 15

```

uses `299 operations`.

**Multiplication Body**

```
assign mult_loop 0
main:
    jic set1 mult_loop addition
    jump end

addition:
    assign temp2 set2
    main_add:
        add ANSWER ANSWER
        assign looper1 0
        assign looper2 0
        jump dec
        cont_add:
            intersect temp2 temp2 looper2
            jne temp2 main_add
            jump end_add
    dec:
        add looper1 looper1
        jidc temp2 looper1 cont_add
        add looper2 looper2
        jump dec
    end_add:
        add mult_loop mult_loop
        jump main

end:

```

For test case

```
* 4 5

```

uses `305 operations` and for test case

```
* 5 4

```

uses `279 operations`.

Therefore my **total score** is `440+299+305+279 =` **`1323`**
> 1 votes

---
Tags: fastest-code, set-theory
---


title: Tips for golfing in Burlesque

text:
# Question
Title: Tips for golfing in Burlesque
This serves as a catalog for tips related to golfing in Burlesque. Burlesque is a lazy, esoteric programming language. It's mostly used on anarchy golf while popularity on Codegolf is not as high. However, this catalog is intended to be used by people golfing on anarchy golf as well.

Please only mention tricks and not obvious shortcuts. An obvious shortcut is for example using `r\` instead of `r@\[` because the built-in `r\` is defined to be `r@\[` and is stated as such in the documentation and is thus just an obvious shortcut.

# Answer
## Using `".. .."wd` instead of `{".."".."}`

If you need a Block of Strings such as `{"abc" "def"}` it is shorter to use the *words* built-in: `"abc def"wd`.

## Using `ra` to parse *fail-safe*

`ps` will fail if the input is not properly formated or might produce unwanted results. In such cases, using `ra` is better.

```
blsq ) "5,"ra
5
blsq ) "5,"ps
{5 ,}
blsq ) "5a"ps
{ERROR: (line 1, column 3):
unexpected end of input}
blsq ) "5a"ra
5

```

## Using `,` to drop stdin

`,` is defined as a pop instruction if and only if there is exactly one element on the stack. It's used to pop STDIN from the stack when it's not needed but there (such as for example is the case on anarchy golf).

## Abusing the way `mo` is defined

`mo` is defined as `1R@\/?*` and is used to generate a Block containing multiples of N:

```
blsq ) 3mo9.+
{3 6 9 12 15 18 21 24 27}

```

Yet due to side effects of `?*` you can do some nasty things with it if you don't provide a number:

```
blsq ) "1"mo9.+
{"11" "21" "31" "41" "51" "61" "71" "81" "91"}

blsq ) {1 2 3 4}mo9.+
{1 4 9 16}

```
> 3 votes

---
Tags: code-golf, tips
---