title: Create xkcd-Style Narrative Charts

text:
# Question
Title: Create xkcd-Style Narrative Charts
In one of the more iconic xkcd strips, Randall Munroe visualised the timelines of several films in narrative charts:

(Click for larger version.)

Source: xkcd No. 657.

Given a specification of the timeline of a movie (or some other narrative), you are to generate such a chart. This is a popularity contest, so the answer with the most (net) votes will win.

## Minimum Requirements

To tighten the spec a bit, here is the minimum set of features every answer must implement:

* Take as input a list of character names, followed by a list of events. Each event is either a list of dying characters, or a list of groups of characters (signifying which characters are currently together). Here is one example for how the Jurassic Park narrative could be encoded:

```
["T-Rex", "Raptor", "Raptor", "Raptor", "Malcolm", "Grant", "Sattler", "Gennaro",
 "Hammond", "Kids", "Muldoon", "Arnold", "Nedry", "Dilophosaurus"]
[
  [[0],[1,2,3],[4],[5,6],[7,8,10,11,12],[9],[13]],
  [[0],[1,2,3],[4,7,5,6,8,9,10,11,12],[13]],
  [[0],[1,2,3],[4,7,5,6,8,9,10],[11,12],[13]],
  [[0],[1,2,3],[4,7,5,6,9],[8,10,11,12],[13]],
  [[0,4,7],[1,2,3],[5,9],[6,8,10,11],[12],[13]],
  [7],
  [[5,9],[0],[4,6,10],[1,2,3],[8,11],[12,13]],
  [12],
  [[0, 5, 9], [1, 2, 3], [4, 6, 10, 8, 11], [13]],
  [[0], [5, 9], [1, 2], [3, 11], [4, 6, 10, 8], [13]],
  [11],
  [[0], [5, 9], [1, 2, 10], [3, 6], [4, 8], [13]],
  [10],
  [[0], [1, 2, 9], [5, 6], [3], [4, 8], [13]],
  [[0], [1], [9, 5, 6], [3], [4, 8], [2], [13]],
  [[0, 1, 9, 5, 6, 3], [4, 8], [2], [13]],
  [1, 3],
  [[0], [9, 5, 6, 3, 4, 8], [2], [13]]
]

```

E.g. the first line means that at the beginning of the chart, T-Rex is a lone, the three Raptors are together, Malcolm is alone, Grant and Sattler are together, etc. The second to last event means that two of the Raptors die.

How exactly you expect the input is up to you, as long as this kind of information can be specified. E.g. you may use any convenient list format. You can also expect the characters in the events to be the full character names again etc.

You may (but don't have to) assume that each list of groups contains each living character in exactly one group. However, you should *not* assume that the groups or characters *within* one event are in particularly convenient order.
* Render to screen or file (as a vector or raster graphic) a chart which has one line for each character. Each line must be labelled with a character name at the beginning of the line.
* For each normal event, there must be, in order, some cross-section of the chart in which the groups of characters are clearly resembled by proximity of their respective lines.
* For each death event, the lines of the relevant characters must terminate in a visible blob.
* You do *not* have to reproduce any other features of Randall's plots, nor do you have to reproduce his drawing style. Straight lines with sharp turns, all in black, without further labels and a title is perfectly fine to enter the competition. There's also no need to use the space efficiently - e.g. you could potentially simplify you algorithm by only ever moving lines downwards to meet up with other characters, as long as there is a discernible direction of time.

I've added a reference solution which fulfils exactly these minimum requirements.

## Making it Pretty

This is a popularity contest though, so on top of that, you may implement whatever fanciness you want. The most important addition is a decent layouting algorithm which makes the chart more legible - e.g. which makes bends in the lines easy to follow and which reduces the number of necessary line crossings. This is the core algorithmic problem of this challenge! The votes will decide how well your algorithm performs at keeping the chart tidy.

But here are some more ideas, most of them based on Randall's charts:

**Decorations:**

* Coloured lines.
* A title for the plot.
* Labelling line ends.
* Automatically relabelling lines which have gone through a busy section.
* Hand-drawn style (or other? as I said, there's no need to reproduce Randall's style if you have a better idea) for lines and fonts.
* Customisable orientation of the time axis.

**Additional Expressiveness:**

* Named events/groups/deaths.
* Disappearing and reappearing lines.
* Characters entering late.
* Highlights which indicate (transferable?) properties of characters (e.g., see the ringbearer in the LotR chart).
* Encoding additional information in the grouping axis (e.g. geographic information like in the LotR chart).
* Time travel?
* Alternative realities?
* A character turning into another?
* Two characters merging? (A character splitting?)
* 3D? (If you *really* go that far, please make sure that you're actually using the additional dimension to visualise someting!)
* Any other relevant features, which could be useful to visualise the narrative of a film (or book etc.).

Of course, many of these will require additional input, and you're free to augment your input format as necessary, but please document how data can be entered.

Please include one or two examples to show off the features you implemented.

Your solution should be able to deal with any valid input, but it's absolutely fine if it's better suited to certain kinds of narratives than others.

## Voting Criteria

I have no illusions that I could tell people how they should spend their votes, but here are some suggested guidelines in order of importance:

* Downvote answers which exploit loopholes, standard ones or others, or hardcode one or more results.
* Do not upvote answers which don't fulfil the minimum requirements (no matter how fancy the rest might be).
* First and foremost, upvote nice layouting algorithms. This includes answers which don't use a lot of vertical space while minimising crossing of lines to keep the graph legible, or which manage to encode additional information into the vertical axis. Visualising the groupings without making a huge mess should be the main focus of this challenge, such that this remains a programming contest with an interesting algorithmic problem at heart.
* Upvote optional features which add expressive power (i.e. are not just pure decoration).
* Lastly, upvote nice presentation.

# Answer
> 18 votes
**Python3 with numpy, scipy and matplotlib**

**edit**:

* I tried to keep the groups in the same relative position between events, hence the `sorted_event` function.
* New function to calculate the y position of the characters (`coords`).
* Every *alive* event is plotted two times now, so the characters stick together better.
* Added legend and removed axes label.

```
import math
import numpy as np
from scipy.interpolate import interp1d
from matplotlib import cm, pyplot as plt

def sorted_event(prev, event):
    """ Returns a new sorted event, where the order of the groups is
    similar to the order in the previous event. """
    similarity = lambda a, b: len(set(a) & set(b)) - len(set(a) ^ set(b))
    most_similar = lambda g: max(prev, key=lambda pg: similarity(g, pg))
    return sorted(event, key=lambda g: prev.index(most_similar(g)))

def parse_data(chars, events):
    """ Turns the input data into 3 "tables":
    - characters: {character_id: character_name}
    - timelines: {character_id: [y0, y1, y2, ...],
    - deaths: {character_id: (x, y)}
    where x and y are the coordinates of a point in the xkcd like plot.
    """
    characters = dict(enumerate(chars))
    deaths = {}
    timelines = {char: [] for char in characters}

    def coords(character, event):
        for gi, group in enumerate(event):
            if character in group:
                ci = group.index(character)
                return (gi + 0.5 * ci / len(group)) / len(event)
        return None

    t = 0
    previous = events[0]
    for event in events:
        if isinstance(event[0], list):
            previous = event = sorted_event(previous, event)
            for character in [c for c in characters if c not in deaths]:
                timelines[character] += [coords(character, event)] * 2
            t += 2
        else:
            for char in set(event) - set(deaths):
                deaths[char] = (t-1, timelines[char][-1])

    return characters, timelines, deaths

def plot_data(chars, timelines, deaths):
    """ Draws a nice xkcd like movie timeline """

    plt.xkcd()  # because python :)

    fig = plt.figure(figsize=(16,8))
    ax = fig.add_subplot(111)
    ax.get_xaxis().set_visible(False)
    ax.get_yaxis().set_visible(False)
    ax.set_xlim([0, max(map(len, timelines.values()))])

    color_floats = np.linspace(0, 1, len(chars))
    color_of = lambda char_id: cm.Accent(color_floats[char_id])

    for char_id in sorted(chars):
        y = timelines[char_id]
        f = interp1d(np.linspace(0, len(y)-1, len(y)), y, kind=5)
        x = np.linspace(0, len(y)-1, len(y)*10)
        ax.plot(x, f(x), c=color_of(char_id))

    x, y = zip(*(deaths[char_id] for char_id in sorted(deaths)))
    ax.scatter(x, y, c=np.array(list(map(color_of, sorted(deaths)))),
               zorder=99, s=40)

    ax.legend(list(map(chars.get, sorted(chars))), loc='best', ncol=4)
    fig.savefig('testplot.png')

if __name__ == '__main__':
    chars = [
        "T-Rex","Raptor","Raptor","Raptor","Malcolm","Grant","Sattler",
        "Gennaro","Hammond","Kids","Muldoon","Arnold","Nedry","Dilophosaurus"
    ]
    events = [
        [[0],[1,2,3],[4],[5,6],[7,8,10,11,12],[9],[13]],
        [[0],[1,2,3],[4,7,5,6,8,9,10,11,12],[13]],
        [[0],[1,2,3],[4,7,5,6,8,9,10],[11,12],[13]],
        [[0],[1,2,3],[4,7,5,6,9],[8,10,11,12],[13]],
        [[0,4,7],[1,2,3],[5,9],[6,8,10,11],[12],[13]],
        [7],
        [[5,9],[0],[4,6,10],[1,2,3],[8,11],[12,13]],
        [12],
        [[0,5,9],[1,2,3],[4,6,10,8,11],[13]],
        [[0],[5,9],[1,2],[3,11],[4,6,10,8],[13]],
        [11],
        [[0],[5,9],[1,2,10],[3,6],[4,8],[13]],
        [10],
        [[0],[1,2,9],[5,6],[3],[4,8],[13]],
        [[0],[1],[9,5,6],[3],[4,8],[2],[13]],
        [[0,1,9,5,6,3],[4,8],[2],[13]],
        [1,3],
        [[0],[9,5,6,3,4,8],[2],[13]]
    ]
    plot_data(*parse_data(chars, events))

```

# Answer
> 6 votes
## T-SQL

I'm not happy with this as an entry, but I think this question deserves at least a try at it. I will try to improve this later time permitting, but labeling will always be a problem in SQL. The solution requires SQL 2012+ and is run in SSMS (SQL Server Management Studio). The output is in the spatial results tab.

```
-- Variables for the input
DECLARE @actors NVARCHAR(MAX) = '["T-Rex", "Raptor", "Raptor", "Raptor", "Malcolm", "Grant", "Sattler", "Gennaro", "Hammond", "Kids", "Muldoon", "Arnold", "Nedry", "Dilophosaurus"]';
DECLARE @timeline NVARCHAR(MAX) = '
[
   [[1], [2, 3, 4], [5], [6, 7], [8, 9, 11, 12, 13], [10], [14]],
   [[1], [2, 3, 4], [5, 8, 6, 7, 9, 10, 11, 12, 13], [14]],
   [[1], [2, 3, 4], [5, 8, 6, 7, 9, 10, 11], [12, 13], [14]],
   [[1], [2, 3, 4], [5, 8, 6, 7, 10], [9, 11, 12, 13], [14]],
   [[1, 5, 8], [2, 3, 4], [6, 10], [7, 9, 11, 12], [13], [14]],
   [8],
   [[6, 10], [1], [5, 7, 11], [2, 3, 4], [9, 12], [13, 14]],
   [13],
   [[1, 6, 10], [2, 3, 4], [5, 7, 11, 9, 12], [14]],
   [[1], [6, 10], [2, 3], [4, 12], [5, 7, 11, 9], [14]],
   [12],
   [[1], [6, 10], [2, 3, 11], [4, 7], [5, 9], [14]],
   [11],
   [[1], [2, 3, 10], [6, 7], [4], [5, 9], [14]],
   [[1], [2], [10, 6, 7], [4], [5, 9], [3], [14]],
   [[1, 2, 10, 6, 7, 4], [5, 9], [3], [14]],
   [2, 4],
   [[1], [10, 6, 7, 5, 9], [3], [14]]
]
';

-- Populate Actor table
WITH actor(A) AS ( SELECT CAST(REPLACE(STUFF(REPLACE(REPLACE(@actors,', ',','),'","','</a><a>'),1,2,'<a>'),'"]','</a>') AS XML))
SELECT ROW_NUMBER() OVER (ORDER BY(SELECT \)) ActorID, a.n.value('.','varchar(50)') Name
INTO Actor
FROM actor CROSS APPLY A.nodes('/a') as a(n);

-- Populate Timeline Table
WITH Seq(L) AS (
    SELECT CAST(REPLACE(REPLACE(REPLACE(REPLACE(@timeline,'[','<e>'),']','</e>'),'</e>,<e>','</e><e>'),'</e>,','</e>') AS XML)
    ),
    TimeLine(N,Exerpt,Elem) AS (
    SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) N
        ,z.query('.')
        ,CAST(REPLACE(CAST(z.query('.') AS VARCHAR(MAX)),',','</e><e>') AS XML)
    FROM Seq
        CROSS APPLY Seq.L.nodes('/e/e') AS Z(Z)
    ),
    Groups(N,G,Exerpt) AS (
    SELECT N,
        ROW_NUMBER() OVER (PARTITION BY N ORDER BY CAST(SUBSTRING(node.value('.','varchar(50)'),1,ISNULL(NULLIF(CHARINDEX(',',node.value('.','varchar(50)')),0),99)-1) AS INT)),
        CAST(REPLACE(CAST(node.query('.') AS VARCHAR(MAX)),',','</e><e>') AS XML) C
    FROM TimeLine
        CROSS APPLY Exerpt.nodes('/e/e') as Z(node)
    WHERE Exerpt.exist('/e/e') = 1
    )
SELECT *
INTO TimeLine
FROM (
    SELECT N, null G, null P, node.value('.','int') ActorID, 1 D
    FROM TimeLine CROSS APPLY TimeLine.Elem.nodes('/e') AS E(node)
    WHERE Exerpt.exist('/e/e') = 0
    UNION ALL
    SELECT N, G, DENSE_RANK() OVER (PARTITION BY N, G ORDER BY node.value('.','int')), node.value('.','int') ActorID, 0
    FROM Groups CROSS APPLY Groups.Exerpt.nodes('/e') AS D(node)
    ) z;

-- Sort the entries again
WITH ReOrder AS (
            SELECT *,
                ROW_NUMBER() OVER (PARTITION BY N,G ORDER BY PG, ActorID) PP,
                COUNT(P) OVER (PARTITION BY N,G) CP,
                MAX(G) OVER (PARTITION BY N) MG,
                MAX(ActorID) OVER (ORDER BY (SELECT\)) MA
            FROM (
                SELECT *,
                    LAG(G,1) OVER (PARTITION BY ActorID ORDER BY N) PG,
                    LEAD(G,1) OVER (PARTITION BY ActorID ORDER BY N) NG
                FROM timeline
                ) rg
    )
SELECT * INTO Reordered
FROM ReOrder;
ALTER TABLE Reordered ADD PPP INT
GO
ALTER TABLE Reordered ADD LPP INT
GO
WITH U AS (SELECT N, P, LPP, LAG(PP,1) OVER (PARTITION BY ActorID ORDER BY N) X FROM Reordered)
UPDATE U SET LPP = X FROM U;
WITH U AS (SELECT N, ActorID, P, PG, LPP, PPP, DENSE_RANK() OVER (PARTITION BY N,G ORDER BY PG, LPP) X FROM Reordered)
UPDATE U SET PPP = X FROM U;
GO

SELECT Name,
    Geometry::STGeomFromText(
        STUFF(LS,1,2,'LINESTRING (') + ')'
        ,0)
        .STBuffer(.1)
        .STUnion(
        Geometry::STGeomFromText('POINT (' + REVERSE(SUBSTRING(REVERSE(LS),1,CHARINDEX(',',REVERSE(LS))-1)) + ')',0).STBuffer(D*.4)
        )
FROM Actor a
    CROSS APPLY (
        SELECT CONCAT(', '
            ,((N*5)-1.2)
                ,' ',(G)+P
            ,', '
            ,((N*5)+1.2)
                ,' ',(G)+P
            ) AS [text()]
        FROM (
            SELECT ActorID, N,
                CASE WHEN d = 1 THEN
                    ((MA+.0) / (LAG(MG,1) OVER (PARTITION BY ActorID ORDER BY N)+.0)) *
                    PG * 1.2
                ELSE
                    ((MA+.0) / (MG+.0)) *
                    G * 1.2
                END G,
                CASE WHEN d = 1 THEN
                (LAG(PPP,1) OVER (PARTITION BY ActorID ORDER BY N) -((LAG(CP,1) OVER (PARTITION BY ActorID ORDER BY N)-1)/2)) * .2
                ELSE
                (PPP-((CP-1)/2)) * .2
                END P
                ,PG
                ,NG
            FROM Reordered
            ) t
        WHERE a.actorid = t.actorid
        ORDER BY N, G
        FOR XML PATH('')
        ) x(LS)
    CROSS APPLY (SELECT MAX(D) d FROM TimeLine dt WHERE dt.ActorID = a.ActorID) d
GO

DROP TABLE Actor;
DROP TABLE Timeline;
DROP TABLE Reordered;

```

The resulting timeline looks like the following

# Answer
> 4 votes
## Mathematica, Reference Solution

For reference, I provide a Mathematica script which fulfils exactly the minimum requirements, nothing more, nothing less.

It expects the characters to be a list of the format in the question in `chars`, and the events in `events`.

```
n = Length@chars;
m = Max@Map[Length, events, {2}];
deaths = {};
Graphics[
 {
  PointSize@Large,
  (
     linePoints = If[Length@# == 3,
         lastPoint = {#[[1]], #[[2]] + #[[3]]/(m + 2)},
         AppendTo[deaths, Point@lastPoint]; lastPoint
         ] & /@ Position[events, #];
     {
      Line@linePoints,
      Text[chars[[#]], linePoints[[1]] - {.5, 0}]
      }
     ) & /@ Range@n,
  deaths
  }
 ]

```

As an example, here is the Jurassic Park example using Mathematica's list type:

```
chars = {"T-Rex", "Raptor", "Raptor", "Raptor", "Malcolm", "Grant",
   "Sattler", "Gennaro", "Hammond", "Kids", "Muldoon", "Arnold",
   "Nedry", "Dilophosaurus"};
events = {
   {{1}, {2, 3, 4}, {5}, {6, 7}, {8, 9, 11, 12, 13}, {10}, {14}},
   {{1}, {2, 3, 4}, {5, 8, 6, 7, 9, 10, 11, 12, 13}, {14}},
   {{1}, {2, 3, 4}, {5, 8, 6, 7, 9, 10, 11}, {12, 13}, {14}},
   {{1}, {2, 3, 4}, {5, 8, 6, 7, 10}, {9, 11, 12, 13}, {14}},
   {{1, 5, 8}, {2, 3, 4}, {6, 10}, {7, 9, 11, 12}, {13}, {14}},
   {8},
   {{6, 10}, {1}, {5, 7, 11}, {2, 3, 4}, {9, 12}, {13, 14}},
   {13},
   {{1, 6, 10}, {2, 3, 4}, {5, 7, 11, 9, 12}, {14}},
   {{1}, {6, 10}, {2, 3}, {4, 12}, {5, 7, 11, 9}, {14}},
   {12},
   {{1}, {6, 10}, {2, 3, 11}, {4, 7}, {5, 9}, {14}},
   {11},
   {{1}, {2, 3, 10}, {6, 7}, {4}, {5, 9}, {14}},
   {{1}, {2}, {10, 6, 7}, {4}, {5, 9}, {3}, {14}},
   {{1, 2, 10, 6, 7, 4}, {5, 9}, {3}, {14}},
   {2, 4},
   {{1}, {10, 6, 7, 4, 5, 9}, {3}, {14}}
};

```

we'll get:

(Click for larger version.)

That doesn't look *too* bad, but that's mostly because the input data is more or less ordered. If we shuffle the groups and characters in each event (while maintaining the same structure), stuff like this can happen:

Which is a bit of a mess.

So as I said, this fulfils only the minimum requirements. It doesn't try to find a nice layout and it isn't pretty, but that's where you guys come in!

---
Tags: popularity-contest, graphical-output, graph-theory
---


title: Meta-atomic code golf

text:
# Question
Title: Meta-atomic code golf
In this meta-challenge, you will score your own submissions. More precisely, you will need to write a program P in language L such that the atomic-score of P is produced by P.

## Score

The idea behind is to count language *tokens* instead of bytes. However, in practice, it is hard to define a general set of rules for all questions (see Count big-ints/symbols/variables as N tokens in atomic-code-golf). That's why it is recommended to clarify rules for each challenge.

Intuitively, tokens are nodes in the abstract syntax tree of your language, except for strings, where each character count (due to potential abuse).

1. Things that count as single tokens:

* variable/function/type identifiers
    * literals, except strings, where each byte counts
    * built-in keywords and operators
    * *(edit)* Empty lists, empty vectors, empty strings
2. Things that are **ignored** from counting:

* preprocessor/reader macros
    * include/import statements
    * *separating* and *grouping symbols* used to build tuples, lists, arrays, statements, function parameters, structs are ignored (`,;:(){}[]<>|`). However, if those symbols are tokens, they count (I am looking at you, CJam (or Brainfuck)). Also, quotes enclosing strings are not counted.
3. Corner cases

* Using identifiers to hold data is a nice hack (see feersum's comment), but it might be considered abusive. So, there should be a penaly of **+25** if your answer exploits identifiers' names for computations. This penalty needs not be correctly scored by your program. If you manage to add a penalty to programs which abuse identifiers' names for computation (for a reasonable subset of programs in your language), you deserve **-100** points of bonus (this bonus needs not be correctly scored by your program).

## Challenge

You should write a program in the language of your choice that scores programs in that language according to the above atomic-score rules. Your own answer will be scored according to that program.

* Input may be read from STDIN or given as a function parameter
* Output is a number, as a return value or printed to STDOUT
* Answer with lowest atomic-score wins
* I'll provide an example answer (if it has the lowest score, the next one wins).

# Answer
> 8 votes
# Unary, 1

The program is a string of `47297560408284` zeroes

**i.e.**

```
000000000000000000000000000000000000000000.... 47297560408284 times

```

A brainfuck quivalent code would be

```
+[>+<+++++]>--.

```

which just prints `1`

as in unary, the whole program is made up of just `0` which are all a single token.

# Answer
> 1 votes
## Common Lisp - ~~23~~ 26

Here is the example answer:

```
(labels ((sum (s form)
           (if (typep form 'sequence)
               (max (1+ s) (reduce #'sum form :initial-value s))
               (1+ s))))
  (defmacro atomic-count (form) (sum 0 form)))

```

And here we can see the macro scoring itself:

```
(atomic-count
 (labels ((sum (s form)
            (if (typep form 'sequence)
                (max (1+ s) (reduce #'sum form :initial-value s))
                (1+ s))))
   (defmacro atomic-count (form) (sum 0 form))))
=> 26

```

NB. This never terminates (or, badly) with cyclic expressions built with `#1=` and `#1#` reader macros.

*(edit) Empty sequences should count as 1 token*

---
Tags: atomic-code-golf
---


# Question
Title: Create a chatbot for the Stack Exchange chatrooms
### The challenge

The goal of this challenge is to create a chatbot that can run in the chatrooms of Stack Exchange. Your bot needs to be able to detect when specific commands are posted by a user and respond to it. This is the list of commands, and what your bot should do:

* `!!newest`: output the title (no link, but the title) of the newest question posted on this site (codegolf.SE).
* `!!metanewest`: output the title of the newest question posted on the meta site (meta.codegolf.SE).
* `!!questioncount`: output the current question count.
* `!!metaquestioncount`: output the current question count on the meta site.
* `!!tag tagname`: output the tag excerpt (the short description) of the tag that's given as the first parameter.
* `!!metatag tagname`: same as above, but for the meta site.
* `!!featured`: output the count of questions that currently have a bounty.
* `!!metafeatured`: output the count of questions that have the \[featured\] tag on Meta.

## Rules

1. You should write a complete program, not a snippet or function.
2. In case it's necessary, you can request username and password as input (prompting for input, STDIN, command-line arguments). This will be necessary if you use, for example, Python or Ruby, but it won't be necessary if you use JavaScript and run the script on the chat room page itself.
3. You are allowed to use external libraries to do stuff like WebSockets. These libraries do not have to count for your character count.
4. You *can* use an external chat wrapper (but you don't have to, writing your own is encouraged), and then that has to count for the character count. You also are not allowed to change the wrapper's code. If you use it, you use it without modifications and all characters have to be counted (that's as a penalty for not writing your own wrapper).

Only the code of the wrapper itself has to count. If there are other files such as examples, these don't have to count.
5. No use of URL shorteners or other ways that can make URLs shorter: the challenge is to golf a chatbot, not to golf a URL.
6. No web requests, except those necessary to chat and to get the information necessary to respond to the commands.
7. Use of the Standard "loopholes" is not allowed.
8. If someone posts a command, you need to respond with a chat message of this format: `@user response`. So, if I write the command `!!featured` and there are 5 featured questions, your bot should post `@ProgramFOX 5`.
9. If I test your bot, I'll run it from my chatbot account and I'll run it in this chatroom. I will always test the bots in that room, so it is not necessary to provide room ID as input, it will always be 14697. This ID won't be given as input, it should be hard-coded.
10. If the command is not found, output `@user The command [command] does not exist`. Replace `[command]` by the name of the non-existing command. If arguments are provided to the command, don't output the arguments, only the command name.
11. If a command has to many arguments, ignore the arguments that are not necessary.
12. If a command has not enough arguments, output `@user You have not provided enough arguments`
13. The system prevents that duplicate messages are posted within a short time range. So, when testing your bot, I will never run two commands that give the same output successively (which means that you do not have to implement a system that makes messages different if they are duplicates, by adding a dot for example).
14. The system prevents that too many messages get posted within a short time range, so when testing, I will never send too many commands within a short time range, which means that your bot does not have to take care of this (by waiting some time before posting, for example).
15. This is , the program with the least amount of bytes wins.

## Getting started

Here is some info to get started with writing your bot. You don't have to use this, but it can be a guidance.

* To log in, first log in to an OpenID provider. This will always be Stack Exchange OpenID (`https://openid.stackexchange.com`). The login form is located at `https://openid.stackexchange.com/account/login`, and provide the username and password there.
* Then, login to `stackexchange.com`. The login form is located at `https://stackexchange.com/users/login`. Choose Stack Exchange as OpenID provider.
* After doing that, log in to chat. The login form for that is located at `http://stackexchange.com/users/chat-login`. Choose Stack Exchange as OpenID provider.
* Then you need to get your `fkey`. For that, go to `http://chat.stackexchange.com/chats/join/favorite` and get the `fkey` from an hidden input field.
* To post a message, send a request to `http://chat.stackexchange.com/chats/14697/messages/new`, and provide two POST parameters: a `text` parameter containing the message text, and a `fkey` parameter containing the `fkey`.
* To see when a new message is posted, you can use WebSockets (but don't have to, feel free to use something else if it's shorter). Please see this Meta Stack Exchange answer:

> ### Chat
>
> `(wss://chat.sockets.stackexchange.com/events/<roomnumber>/<somehash>?l=<timethingy>)`
>
> The hash can be fetched by POSTing the room id and fkey to `http://chat.stackexchange.com/ws-auth`
>
> The timethingy is the time key of the json returned by `/chats/<roomno>/events`.

The event ID when a message is posted is `1`.
* It is useful to look at the existing chat-wrappers, such as Doorknob's StackExchange-Chatty and Manishearth's ChatExchange, to see how it exactly works.

# Answer
# JavaScript + jQuery, ~~1362~~ 1258 bytes

Golfed using a minifier:

```
$(function(){function e(){function e(e,t){$("#input").val("@"+$(e).parents(".user-container").find(".username").eq(0).text()+" "+t),$("#sayit-button").click()}var i,a=$(t),s=a.map(function(e,t){return t.id}),r=s.slice(-1)[0]
n!=r&&(i=a.slice($.inArray(n,s)+1),n=r,i.map(function(t,n){var i,a,s,r,o,u,c,f=n.textContent.match(/!!(\S+)(?:\s+(\S+))?/)
if(f){switch(i=f[1],a=f[2],s="codegolf",0==i.indexOf("meta")&&(s="meta."+s,i=i.slice(4)),r="?site="+s,c=0,i){case"newest":o=["questions","&order=desc&sort=creation"],u=function(e){return e.items[0].title}
break
case"questioncount":o=["info",""],u=function(e){return e.items[0].total_questions}
break
case"tag":if(!a){c=1
break}o=["tags/"+a+"/wikis",""],u=function(e){return 0==e.items.length?"Tag not found":e.items[0].excerpt}
break
case"featured":o=0==s.indexOf("meta.")?["questions","&tagged=featured"]:["questions/featured",""],u=function(e){var t=e.items.length
return(e.items.has_more?"more than ":"")+t}}c?e(n,"You have not provided enough arguments"):o?$.get("http://api.stackexchange.com/2.2/"+o[0]+r+o[1],function(t){e(n,u(t))}):e(n,"The command "+i+" does not exist")}}))}var t="[id^=message-]",n=$(t).eq(-1).attr("id")
new MutationObserver(e).observe($("#chat").get(0),{childList:!0,subtree:!0})})

```

You have to run the script directly in the browser (using Stack Exchange's jQuery works):

1. Open http://chat.stackexchange.com/rooms/14697/chatbot-challenge-on-programming-puzzles-code-golf
2. Paste the above code in the console
3. Enter some commands in the chat

It could be golfed a lot more, but couldn't be bothered.

---

Un-golfed:

```
$(function() {
    var sel = '[id^=message-]';
    var latestMessage = $(sel).eq(-1).attr('id');
    function update() {
        var messages = $(sel);
        var ids = messages.map(function(i, x) { return x.id; });
        var newest = ids.slice(-1)[0];
        if(latestMessage == newest) {
            return;
        }
        var newMessages = messages.slice($.inArray(latestMessage, ids) + 1);
        latestMessage = newest;
        newMessages.map(function(i, x) {
            var m = x.textContent.match(/!!(\S+)(?:\s+(\S+))?/);
            if(!m) {
                return;
            }
            var c = m[1];
            var a = m[2];
            var s = 'codegolf';
            if(c.indexOf('meta') == 0) {
                s = 'meta.' + s;
                c = c.slice(4);
            }
            var site = '?site=' + s;
            var url;
            var extractor;
            var too_few_args = 0;
            switch(c) {
                case 'newest':
                    var url = ['questions', '&order=desc&sort=creation'];
                    extractor = function(data) {
                        return data.items[0].title;
                    };
                    break;
                case 'questioncount':
                    url = ['info', ''];
                    extractor = function(data) {
                        return data.items[0].total_questions;
                    };
                    break;
                case 'tag':
                    if(!a) {
                        too_few_args = 1;
                        break;
                    }
                    url = ['tags/' + a + '/wikis', ''];
                    extractor = function(data) {
                        if(data.items.length == 0) {
                            return 'Tag not found';
                        }
                        return data.items[0].excerpt;
                    };
                    break;
                case 'featured':
                    url = s.indexOf('meta.') == 0? ['questions', '&tagged=featured']: ['questions/featured', ''];
                    extractor = function(data) {
                        var l = data.items.length;
                        return (data.items.has_more? 'more than ': '') + l;
                    }
                    break;
            }
            if(too_few_args) {
                write(x, 'You have not provided enough arguments');
            } else if(!url) {
                write(x, 'The command ' + c + ' does not exist');
            } else {
                $.get('http://api.stackexchange.com/2.2/' + url[0] + site + url[1], function(data) {
                    write(x, extractor(data));
                });
            }
        });

        function write(x, m) {
            $('#input').val('@' + $(x).parents('.user-container').find('.username').eq(0).text() + ' ' + m);
            $('#sayit-button').click();
        }
    }
    new MutationObserver(update).observe($('#chat').get(0), {childList: true, subtree: true});
});

```
> 17 votes

---
Tags: code-golf
---


# Question
Title: Squarefinder – Locating regular tetragons
Imagine a bunch of rectangles drawn in the plane, each rectangle with its vertices at integer coordinates and its sides parallel to the axes:

The rectangles partition the plane into a number of disjoint regions, coloured red and blue below:

Your goal is to find the number of such regions which are perfect squares. In the example above, there are three:

Note that the big square in the middle is not counted as it is not a single region, but is instead made up of several smaller disjoint regions.

## Input

You may write a function or a full program for this challenge.

Input will be `4n` nonnegative integers defining `n` rectangles in the plane. Each rectangle is represented by two opposing vertices, e.g. `4 9 7 8` represents the rectangle with opposing vertices `(4, 9)` and `(7, 8)`. Note that this rectangle could also be represented as `7 8 4 9` or `4 8 7 9`.

The exact input format is flexible (e.g. space-separated string, comma-separated string, single array of integers, list of coordinate tuples, and so on) but please be reasonable and give an example of how to run your code in your post. You may not reorder the input.

For simplicity, you can assume that no two edges will be overlapping — this includes overlapping at a vertex. In particular, this implies that no two rectangles will be touching edge-to-edge or corner-to-corner, and the rectangles will have nonzero area.

## Output

Your program should print or return a single integer, which is the number of square regions.

## Scoring

This is code golf, so the code in the fewest bytes wins.

---

## Test cases

**Input:**

```
0 0 5 5
6 8 10 4
14 16 11 13
19 1 18 2

```

**Output:**

```
4

```

This is simply four disjoint squares:

---

**Input:**

```
2 1 3 11
1 10 5 19
6 10 11 3
8 8 15 15
13 13 9 5
15 1 19 7
17 19 19 17

```

**Output:**

```
3

```

This is the example test case at the start of the post.

---

**Input:**

```
0 9 15 12
6 3 18 15
9 6 12 20
13 4 17 8

```

**Output:**

```
7

```

---

**Input:**

```
5 9 11 10
5 12 11 13
6 8 7 14
9 8 10 14
13 8 14 9
13 10 14 14

```

**Output:**

```
14

```

---

**Input:**

```
0 99999 100000 0

```

**Output:**

```
0

```

This is just one big rectangle.

---

**Input:**

```
0 99999 100000 0
2 1 142857 285714

```

**Output:**

```
1

```

Two big rectangles which overlap.

# Answer
## SQL (POSTGIS), ~~286~~ ~~269~~ ~~261~~ ~~240~~ ~~226~~ ~~218~~ 216

This is a query for the PostGIS extension to PostgreSQL. I haven't counted the input values in the total.

```
SELECT SUM(1)FROM(SELECT(ST_Dump(ST_Polygonize(g))).geom d FROM(SELECT ST_Union(ST_Boundary(ST_MakeEnvelope(a,b,c,d)))g FROM(VALUES
-- Coordinate input
(2, 1, 3, 11)
,(1, 10, 5, 19)
,(6, 10, 11, 3)
,(8, 8, 15, 15)
,(13, 13, 9, 5)
,(15, 1, 19, 7)
,(17, 19, 19, 17)
)i(a,b,c,d))i)a WHERE(ST_XMax(d)-ST_XMin(d))^2+(ST_YMax(d)-ST_YMin(d))^2=ST_Area(d)*2

```

**Explanation**

The query builds geometries for each coordinate pair. Unions the exterior rings to properly node the lines. Turns the results into polygons and tests ~~the width against height and~~ the area doubled against the sum of each side squared.

It will run as a standalone query on any PostgreSQL database with the PostGIS Extension.

**Edit** Found a couple more.
> 10 votes

# Answer
# Python 2, ~~480 436 386~~ 352 bytes

```
exec u"""s=sorted;H=[];V=[]
FRIinput():
 S=2*map(s,zip(*R))
 FiI0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    FeIs(H):
     C,(A,B)=e
     if a<C<b&A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D)&c==C==(b,B)&B-b==D-d&1-any(d<X[0]<D&b<y<B Fy,XIH)Fb,aIH FB,AIH Fd,cIV FD,CIV)""".translate({70:u"for ",73:u" in ",38:u" and "})

```

Takes a list of coordinate pairs through STDIN in the format:

```
[  [(x, y), (x, y)],  [(x, y), (x, y)],  ...  ]

```

and prints the result to STDOUT.

The actual program, after string replacement, is:

```
s=sorted;H=[];V=[]
for R in input():
 S=2*map(s,zip(*R))
 for i in 0,1,2,3:
    c=S[i][i/2];a,b=S[~i]
    for e in s(H):
     C,(A,B)=e
     if a<C<b and A<c<B:e[:]=C,(A,c);H+=[C,(c,B)],;V+=[c,(a,C)],;a=C
    V+=[c,(a,b)],;H,V=V,H
print sum(a==A==(d,D) and c==C==(b,B) and B-b==D-d and 1-any(d<X[0]<D and b<y<B for y,X in H)for b,a in H for B,A in H for d,c in V for D,C in V)

```

## Explanation

Instead of fiddling with complex polygons, this program deals with simple line segments. For each input rectangle, we add each of its four edges to a collective segment list, individually. Adding a segment to the list goes as follows: we test each of the existing segments for intersection with the new segment; if we find an intersection, we divide both segments at the point of intersection and continue. To make things easier, we actually keep two separate segment lists: a horizonal one and a vertical one. Since segments don't overlap, horizontal segments can only intersect vertical segments and vice versa. Better yet, it means that all intersections (not considering the edges of the same rectangle) are "proper," i.e., we don't have T-shaped intersections, so "both sides" of each segment are truly divided.

Once we've constructed the segment list(s), we start counting squares. For each combination of four segments (particularly, two horizontal segments and two vertical ones,) we test if they form a square. Furthermore, we verify that no vertex lies within this square (which can happen if, for example, we have a small square inside a bigger one.) This gives us the desired quantity. Note that even though the program tests each combination four times in different orders, the particular ordering of the segment coordinates guarantees that we count each square only once.
> 14 votes

# Answer
# Haskell, ~~276 266 250 237 225 222~~ 217 bytes

It keeps getting shorter... and more obfuscated.

```
(x#i)l=mapM id[[min x i..max x i-1],l]
(y!j)l f=and[p l==p(f[y,j])|p<-map elem$f[y..j]]
s[h,v]=sum[1|[x,j]<-h,[y,i]<-v,x<i,i-x==j-y,(y!j)h$x#i,(x!i)v$y#j]
n=s.foldr(\(x,y,i,j)->zipWith(++)[x#i$[y,j],y#j$[x,i]])[[],[]]

```

Evaluate `n [(0,0,5,5),(6,8,10,4),(14,16,11,13),(19,1,18,2)]` for the first test case. I think I'm getting close to the limits of golfing this algorithm on Haskell.

This function is so slow (at least *O(n3)* where *n* is the total perimeter of all rectangles in the input) that I cannot evaluate it on the last two test cases. When I compiled it with optimizations turned on and run it on the 400-times shrunk version `[(0,249,250,0),(2,1,357,714)]` of the last test, it finished in a little over 12 seconds. Based on this, the actual test case would finish in about 25 years.

### Explanation (partial, I will expand this when I have time)

We first build two lists `h` and `v` as follows. For each rectangle in the input, we split its border into segments of length 1. The west endpoints of horizontal segments are stored in `h`, and the south endpoints of vertical segments in `v`, as lists `[x,y]` of length 2. The coordinates in `v` are stored in a reversed form as `[y,x]` for golfing reasons. Then we just loop over both lists and search for horizontal edge `[x,j]` and vertical edge `[i,y]` such that `x < i` and `i-x == j-y` (so they are the northwest and southeast corners of a square), and check that the borders of the square are in the correct lists `h` and `v`, while the interior coordinates are not. The number of the positive instances of the search is the output.
> 5 votes

---
Tags: code-golf, geometry
---


title: Use threes to count the threes!

text:
# Question
Title: Use threes to count the threes!
Write a program or function that takes two numbers - `x>3` and `n>0` \- as input, and finds all possible bases `b` where the digit `3` appears at least `n` times in `(x in base b)`.

Input and output may be through command line or function arguments, stdin/stdout, graphical input/output, error messages, function returns, etc.

The code must consist entirely of three-symbol "words", where each symbol is a letter or number (in printable ASCII) and the words are each separated by one non-alphanumeric printable ASCII character or newline (see example). Furthermore, adding a space into any of the words must ruin the program.

Shortest code wins.

# Example

The following code meets the first part of the specs (but doesn't actually work):

```
abc 123 fwe[3gY]4fs-es3=13N
338 w3W|W2w

```

# Test Cases

`5 1` -\>

`8 1` -\> `5`

`23 1` -\> `4 5 6 7 10 20`

`15 2` -\> `4`

`111 2` -\> `4 6 9 36`

`819 3` -\> `4 16`

A test program written in Java 8 can be found at http://pastebin.com/E8GpHbfB.

# Answer
# BBC Basic, 207 bytes

BBC Basic allows you to abbreviate keywords by ending them with a period (e.g., `PRINT``PRI.`, `REPEAT``REP.`). I should really be using a named procedure here instead of a function declaration, but abbreviating `DEF PROC_whatever` to `DEF PRO.` just isn't going to work.

The rules make it impossible to use an `IF` statement, so instead I'm calculating the target line of a `GOTO` statement based on the result of a comparison. (In BBC Basic, `true` has a value of –1, so `101-ZIP` is equal to 102 if `ZIP` is true, and 101 otherwise.)

The last line (`103=000`) ends the function definition and returns a value of zero.

Tested on BeebEm3. Lines 10–60 are excluded from the byte count.

```
10 READ X,N : IF X=0 THEN END
20 PRINT "x=";X;", n=";N
30 A = FNX(X,N)
40 GOTO 10
50 DATA 5,1,8,1,23,1,15,2,111,2,819,3,0,0
60 REM -------------------
100 DEF FNX(FOO,BAR)BAZ=004:REP.BAT=000:QUX=FOO:REP.XXD=QUX MOD BAZ:ZAP=XXD=003:BAT=BAT-ZAP:QUX=QUX-XXD:QUX=QUX/BAZ:UNT.QUX=000:ZIP=BAT<BAR:ZIP=101-ZIP:GOT.ZIP
101 PRI.BAZ
102 BAZ=BAZ+001:UNT.BAZ=FOO
103=000

```
> 8 votes

# Answer
# CJam, 108 bytes

```
097{sLo,Lso=rii*rii:MLo;Lso_Lso,002>Lso{001$Lso\Lob{003=Lso}Lso,Lso,MLo(Lso>Lso}Lso,Lso\Lso;LoS*Lso}000$001*

```

It will not stop people using CJam...
> 4 votes

# Answer
# Haskell, 219

```
003&bbb=001
nnn&bbb|bbb>nnn=000|000<111=mod nnn bbb&bbb+div nnn bbb&bbb
nnn%xxx=ggo nnn 004 xxx
ggo nnn bbb xxx|bbb>nnn=get[nnn]nnn|nnn&bbb>xxx-001=bbb:ggo nnn(bbb+001)xxx|000<111=ggo nnn(bbb+001)xxx
get(xxx:sss)bbb=sss

```

call like `8 % 1`.

I mostly just used three-letter / operator names, but it was tricky to get an empty list (`[]`).
> 3 votes

# Answer
# C - 252 characters

Will admit `C` is not the best language for this, and had to cheat a little bit...

To compile, save as `fit.c` then `gcc -D___=/**/ -o fit fit.c`

The function `fit` can be all concatenated on one line, but I thought it looked nicer and fit in with the *threeness* of the challenge by formatting in lines of 9 (=3×3) token/punctuation pairs. The hardest part was figuring out a way to check for `== 3` without using `==`!

```
// The function I'm counting...

fit(int not,int fin,int*rot)___{int
nor,fir,nit,ton,tin,ion;for(nor=004;
nor<not;nor=nor+001)___{for(nit=not,
fir=000;nit>000;nit=nit/nor)tin=nit%
nor,ion=tin<003|tin>003,ion=ion?000:
001,fir=fir+ion;ton=fir<fin,ton=ton?
000:001;rot[nor]___=ton;___}___ ___}

// This is the code to call the function...

#include <stdio.h>

main()
{
    int a[999];
    int X[6] = {5, 8, 23, 15, 111, 819};
    int N[6] = {1, 1, 1, 2, 2, 3};

    int i, j;

    for (i = 0; i < 6; i++)
    {
        fit(X[i], N[i], a);

        printf("%d %d ->", X[i], N[i]);

        for (j = 4; j < X[i]; j++)
            if (a[j]) printf(" %d", j);

        printf("\n");
    }

    return 0;
}

```

Output is per specs:

```
5 1 ->
8 1 -> 5
23 1 -> 4 5 6 7 10 20
15 2 -> 4
111 2 -> 4 6 9 36
819 3 -> 4 16

```
> 2 votes

---
Tags: code-golf, math, restricted-source, base-conversion
---


title: Draw the Warm Welcome Secret Hat

text:
# Question
Title: Draw the Warm Welcome Secret Hat
Winter Bash 2014 is on its prime and don't we all love the hats? Especially the secret hats!

So why not draw one of secret hats?

## The challenge

Your task is to draw the Warm Welcome Hat in proportion, in a language of your choice and having an exact construction as appearing on this page.

As always, you can render the hat to a file or screen using vector or raster graphics. If your output is rasterised, your image must have dimensions of 400x400 pixels or more.

Moreover, the actual contents of the hat (the area of the bounding rectangle of the colored parts of the image) should cover more than 40% of your output image.

## Specifications

The image below lists out various dimensions of the hat. All dimensions are in the unit, for example, pixels. All border radius in the image are to be drawn with a radius of `13` units.

**Colors**:

* Red in the star and circular ring - rgb(255, 28, 34)
* Yellow in the circle - rgb(255, 202, 87)
* Lightest grey - rgb(88, 88, 92)
* Darkest grey - rgb(31, 26, 26)
* Middle grey - rgb(64, 64, 64)

## Scoring

This is code golf, so the shortest answer (in bytes) wins.

As a word of warning, using existing compression (like embedding a compressed GIF) falls into several standard loopholes.

# Answer
## GolfScript (376 373 364 350 *or 645 610 607* bytes)

Following the *original* specification, which called for the exact construction of the SVG, a golfed SVG is generated in 607 bytes.

Code contains lots of non-printing characters, so here's the xxd output:

```
0000000: 221a c837 cde6 0c0c 4658 5786 cead ca66  "..7....FXW....f
0000010: 3507 d130 1577 4657 4067 df6b 97e7 510f  5..0.wFW@g.k..Q.
0000020: cbb0 e3e5 77c6 a91d d830 fa92 eea0 d447  ....w....0.....G
0000030: 7721 cc59 3f4c 230b e0bb fd3e ecf3 d4f7  w!.Y?L#....>....
0000040: 2c6b abd5 b1e5 939d 68b4 e89e 39ca a259  ,k......h...9..Y
0000050: b934 ef6f 203a 7abf 1a2c b468 3351 4c53  .4.o :z..,.h3QLS
0000060: c056 9a59 f38c a97e cf82 8840 ee7c 43e4  .V.Y...~...@.|C.
0000070: 123f df1a 00d4 542d a29c 0195 3ad5 4af4  .?....T-....:.J.
0000080: c644 57c7 0b6b 4d4f 908b 8cf7 c8e2 536d  .DW..kMO......Sm
0000090: 9d36 1139 1406 5c5c dcbc 3a11 1993 63a6  .6.9..\\..:...c.
00000a0: 4f8b 7b62 de77 5158 a485 dec1 87b4 1d11  O.{b.wQX........
00000b0: 01b1 e49d 8adb 0b29 ad44 93e4 7bbd 027e  .......).D..{..~
00000c0: 7a6f 60ca 99f4 6ab3 7bc0 63c3 ba70 1220  zo`...j.{.c..p.
00000d0: 1aea 9206 da5a 95ce 6f70 67f8 856e 8807  .....Z..opg..n..
00000e0: adec e533 0c1e 3dc6 96e5 54d4 2837 4497  ...3..=...T.(7D.
00000f0: f5ea 2135 d261 9c02 fa61 c12a 7180 085a  ..!5.a...a.*q..Z
0000100: a5b8 e3d6 68cb 0659 f4ad d01d 5fc4 9e5b  ....h..Y...._..[
0000110: d030 46d5 96c4 439f da99 2cb1 52b9 5d53  .0F...C...,.R.]S
0000120: 098e 7598 2785 a962 a40d edbd 18cb e46c  ..u.'..b.......l
0000130: 6edb ba9f 17be 36ab ef23 0caf 3ce8 352d  n.....6..#..<.5-
0000140: fad5 762b a388 ca17 413f 7dac 6dd1 116e  ..v+....A?}.m..n
0000150: b2e8 9cd1 d00a dda1 716d a148 acc7 8749  ........qm.H...I
0000160: f2c3 a7a9 8128 02e9 d83c f350 7a02 74ec  .....(...<.Pz.t.
0000170: 6270 6089 a16d 7bfa b6dd e56a 366a d85b  bp`..m{....j6j.[
0000180: 33e5 b777 05c1 6f4e f06b ca95 3ffc 49f7  3..w..oN.k..?.I.
0000190: 1a08 6bc5 abb0 c745 e439 b87e b81c 52c8  ..k....E.9.~..R.
00001a0: a445 935e 5c5c 00d3 34de c002 721c b69d  .E.^\\..4...r...
00001b0: 16ee aab0 9562 4d44 44ed 0193 13a7 eed2  .....bMDD.......
00001c0: 99e4 6350 a756 c21a 980b 6bca 57f9 8443  ..cP.V....k.W..C
00001d0: eecc 9fd1 05ce 78c4 f95f dc90 8926 6eb4  ......x.._...&n.
00001e0: 88b8 7b90 44be 33c3 cc2a b032 d809 17d0  ..{.D.3..*.2....
00001f0: 7e32 c4c9 e37f ceb3 b1e0 b634 a690 8163  ~2.........4...c
0000200: cd34 e3d9 9768 3e13 ac10 5003 1cb7 af6b  .4...h>...P....k
0000210: 863f cba0 9896 e50a d029 8e2b 584c d86f  .?.......).+XL.o
0000220: 67a7 120e 318a cb22 3235 3662 6173 6520  g...1.."256base
0000230: 3132 3462 6173 655b 305d 2f28 3332 2c7b  124base[0]/(32,{
0000240: 5c5b 3124 295d 2f5c 3224 3d2a 7d2f 5c2c  \[1$)]/\2$=*}/\,
0000250: 297b 2d2e 3634 3e33 322a 2b7d 2b25 2b    ){-.64>32*+}+%+

```

It's a variant on the constructive grammar engine which followers of will be familiar with:

```
'MAGIC STRING'256base 124base[0]/(40,{\[1$)]/\2$=*}/\,){-.64>32*+}+%+

```

It turned out to be slightly better to upper-case the golfed SVG, compress that, and then lower-case after decompression.

When run it produces an 840-byte SVG:

```
<svg width="192" height="192"><g transform="translate(-19.356 39.823) scale(.11435537421402706)"><path d="m873 126c-28-56-97-79-153-50l-361 182c-40 20-63 60-62 102v369c0 63 51 114 114 114h1198c63 0 114-51 114-114v-369c1-62-22-82-62-102l-361-182c-56-29-125-6-153 50c-28 56-6 124 49 152h-372c55-28 77-96 49-152z" fill="#231f20"/><path d="m1642 812c0 60-49 109-109 109h-1047c-60 0-109-49-109-109v-435c0-60 49-109 109-109h96.557636322653a530 274 0 0 1 854.884727354693 0h96.557636322653c60 0 109 49 109 109v435z" fill="#424143"/><path d="m1561 826c0 52-42 95-95 95h-912c-52 0-95-42-95-95v-463c0-52 42-95 95-95h912c52 0 95 42 95 95v463z" fill="#595a5c"/><circle cy="594" cx="1010" r="199" fill="#f9c960" stroke="#ec2227" stroke-width="42"/><path d="m1063 615l85-62-105 0-33-100-33 100-105 0 85 62-32 100 85-62 85 62z" fill="#ec2227"/></g></svg>

```

I've tweaked the position by a few millipixels and corrected one small asymmetry in the darkest grey part.

---

But the changes to the question and discussion in chat indicate that it's actually permissible to create a good approximation to the SVG, which can be done in 364 bytes. The decompression chain is similar, so the xxd output of the GolfScript file is:

```
0000000: 2710 9f1d b7bb 6ca9 ad60 1325 b869 45a6  '.....l..`.%.iE.
0000010: 9371 2eee 1271 1dac 0244 9ca3 2820 e6be  .q...q...D..( ..
0000020: b038 68e4 4e53 bbe9 7809 a67a 5f02 2f14  .8h.NS..x..z_./.
0000030: 66a1 0cb3 648c 76d4 0450 028d fd32 b81f  f...d.v..P...2..
0000040: 351a d449 bba8 e685 4de8 1fc0 abfd 8b9f  5..I....M.......
0000050: d9d9 33cd 16e9 5c27 b7a0 dc0f 4138 a2ca  ..3...\'....A8..
0000060: 2b45 a2c2 571e 7e1e 1030 dcfd b48e 377b  +E..W.~..0....7{
0000070: 112e 7762 d14c 1fed 0bcb 15b4 c383 f828  ..wb.L.........(
0000080: b317 8c9f 890b ce84 7782 4c10 fc8e 7602  ........w.L...v.
0000090: 9fef 9563 fe30 45b0 7144 30b3 f3c5 fa22  ...c.0E.qD0...."
00000a0: ccae 8a08 c506 466b 6b84 317e 62dd a558  ......Fkk.1~b..X
00000b0: 8423 d8ef 9d67 e807 0d23 847d 4dab 68ff  .#...g...#.}M.h.
00000c0: 952b ca20 14d3 0881 2880 6611 eb53 10c6  .+. ....(.f..S..
00000d0: 0058 573f 3c87 957c 8512 59ff 94f3 ae38  .XW?<..|..Y....8
00000e0: 4145 bf8d 4123 6e84 aa62 904d a878 0bca  AE..A#n..b.M.x..
00000f0: 854b deaa 32ae 70fc b31a 9578 676a df8a  .K..2.p....xgj..
0000100: 7310 ecfc 47d2 5dde 1a8c 3898 943b ede3  s...G.]...8..;..
0000110: d0a2 55a4 eb00 b623 0302 d79c a712 b616  ..U....#........
0000120: 5037 dc2d 0dad 2732 3536 6261 7365 2031  P7.-..'256base 1
0000130: 3133 6261 7365 5b30 5d2f 2832 312c 7b5c  13base[0]/(21,{\
0000140: 5b31 2429 5d2f 5c32 243d 2a7d 2f5c 2c29  [1$)]/\2$=*}/\,)
0000150: 7b2d 2e36 343e 3332 2a2b 7d2b 252b       {-.64>32*+}+%+

```

and generates a 547-byte SVG file:

```
<svg width="1426" height="858"><path d="m475 114-361.5 182v370h1199v-370l-361.5-182" stroke="#231f20" stroke-linecap="round" stroke-linejoin="round" stroke-width="227"/><ellipse cx="713" cy="367" rx="530" ry="274" fill="#424143"/><rect x="80" y="205" width="1266" height="653" rx="109" ry="109" fill="#424143"/><rect x="161" y="205" width="1103" height="653" rx="95" ry="95" fill="#595a5c"/><circle cx="713" cy="531" r="199" fill="#f9c960" stroke="#ec2227" stroke-width="42"/><path d="m713 390 85 262-223-162 276 0-223 162z" fill="#ec2227"/></svg>

```

Thanks to Paul LeBeau for pointing out a 7-byte saving in the SVG which translated to 9 bytes in the GolfScript, and for his answer which demonstrated that the star can be drawn with just the 5 points. (Using his answer I could get down to 329 bytes, or 323 with some tweaking to his answer, but I'm not comfortable with that).

Exported at 50% with Inkscape:

To see the structure, here's the SVG rendered with `fill="none"` on everything and some fill colours changed to stroke colours:
> 15 votes

# Answer
## SVG (462 460 454 429 384 365 bytes)

I know it isn't a programming language, but I thought this will at least be useful to anyone generating SVG output...

This is based on Peter Taylor's SVG.

By using the original coords, and optimizing the paths a little, I managed to shrink the SVG down. I also fixed the colours.

```
<svg><g stroke-linecap=round stroke-linejoin=round stroke-width=26><path d=M54,13,13,36V75H151V36L110,13 stroke=#1f1a1a /><path d=M21,84V36H37A91,91,0,0,1,127,36h16V84z stroke=#404040 /><path d=M30,36v48h104V36z stroke=#58585c fill=#58585c /></g><circle cx=82 cy=60 r=23 fill=#ffca57 stroke=#ff1c22 stroke-width=5 /><path d=M82,43,92,74,66,55H98L72,74z fill=#ff1c22
```

**Update:** Fixed flaw pointed out by Peter Taylor and position of rects and saved 2 more bytes.

**Update 2:** Incorporated another fix and suggestions from Peter (-6 bytes)

**Update 3:** Just noticed the instructions now specify all radii are 13, so taking advantage of that, and optimizing the paths a bit more, I saved another 25 bytes. More readable fiddle here.

**Update 4:** Since I am already assuming the SVG is embedded in HTML (standalone SVGs need the namespace declaration), I can actually squeeze this more. (a) I don't need the width and height attributes because the size of the SVG is smaller than the default size browsers give to objects whose size is indeteminate (300x150), and (b) the HTML parser is forgiving about attributes which don't have quotes, so some of them can be removed (idea from Squeamish Ossifrage). Saves another 45 bytes.

**Update 5:** Using hsl's tricks for de-quoting the colours and dropping the trailing end tags. We saved another 19 bytes. The latter seemed a bit cheaty to me at first, but since it works in all browsers, I changed my mind. :) Thanks hsl!
> 26 votes

# Answer
# Mathematica ~~787 612 600 514~~ 506 bytes

Surprising amount of code needed. Will surely be beaten.

**Ungolfed form**

```
red=RGBColor[1.,.11,.13]
yellow=RGBColor[1.,.79,.34]
lightGrey=RGBColor[.35,.35,.36]
midGrey=RGBColor[.25,.25,.25]
r=RoundingRadius->8;
pentagonalVertices[offset_]:=Table[{Cos[2π k/5+ offset],Sin[2π k/5+offset]},{k,0,5}];
x=63;x2=72;
y=37;
pts={{e=22,50},{h=72,30},{h,-17},{-h,-15},{-h,30},{-e,50}};
pts2={{-h,-15},{-h,30},{-e,50}}
Graphics[{
{Black,Thickness[.13],JoinForm["Round"],CapForm["Round"], Line[pts]},
midGrey,Rectangle[{-x2,-y},{x2,y},r],
Disk[{0,-55},104,{Pi/3,2Pi/3}],
White,Rectangle[{-40,-60},{40,0},r],
lightGrey,Rectangle[{-x,-y},{x,y},r],
red,Disk[{0,0},25],yellow,Disk[{0,0},19.5],red,
GraphicsComplex[16.7 pentagonalVertices[Pi/2],Polygon[{1,3,5,2,4}]],
GraphicsComplex[6.4 pentagonalVertices[3 Pi/2],Polygon[{1,2,3,4,5}]]}]

```

## Golfed

```
g=GraphicsComplex;c=RGBColor;d=c[1.,.11,.13];o="Round";k=Rectangle;j=Disk;n=Polygon;r=RoundingRadius->8;w@s_:=Table[{Cos[2\[Pi]k/5+s],Sin[2\[Pi]k/5+s]},{k,0,5}];x=63;i=72;y=37;p={{e=22,50},{h=72,30},{h,-17},{-h,-15},{-h,30},{-e,50}};Graphics[{Thickness[.13],JoinForm@o,CapForm@o,Line@p,c[.25,.25,.25],k[{-i,-y},{i,y},r],j[{0,-55},104,{\[Pi]/3,2\[Pi]/3}],White,k[{-40,-60},{40,0},r],c[.35,.35,.36],k[{-x,-y},{x,y},r],d,j[{0,0},25],c[1.,.79,.34],j[{0,0},19.5],d,g[16.7w[\[Pi]/2],n[{1,3,5,2,4}]],g[6.4w[3\[Pi]/2],n[{1,2,3,4,5}]]}]

```
> 20 votes

# Answer
## HTML + ES6, 533

```
<canvas id=D width=600 height=400><script>c=D.getContext('2d')
S=x=>c.strokeStyle=F(x)
F=x=>c.fillStyle=x
W=x=>c.lineWidth=x
B=x=>c.stroke()||c.fill()||c.beginPath()
G='s.charCodeAt(i++)*9-300,'
L=s=>B()||eval('for(i in s)i%2||c.lineTo('+G+G+'0)')&&B()
c.lineCap=c.lineJoin='round'
W(60)
S('#1F1A1A')
L(';,+3+BXBX3H,')
S('#404040')
L('.3.EUEU3.3')
c.arc(291,390,270,4,5.2,0)
B()
S('#58585C')
L('131ERER313')
S(R='#FF1C22')
F('#FFCA57')
W(30)
c.arc(291,240,69,0,7,0)
B()
c.font='105px serif'
S(R)
c.fillText('\u2605',239,276)</script>

```

Snippet (modified):

```
<canvas style="margin:-40px 0 0 100px;height:250px;" id=D width=600 height=400><script>stages=[function(){c=D.getContext('2d');S=function(x){return c.strokeStyle=F(x)};F=function(x){return c.fillStyle=x};W=function(x){return c.lineWidth=x};B=function(x){return c.stroke()||c.fill()||c.beginPath()};G='s.charCodeAt(i++)*9-300,';L=function(s){return B()||eval('for(i in s)i%2||c.lineTo('+G+G+'0)')&&B()}},function(){c.lineCap=c.lineJoin='round';W(60);S('#1F1A1A');L(';,+3+BXBX3H,')},function(){S('#404040');L('.3.EUEU3.3')},function(){c.arc(291,390,270,4,5.2,0);B()},function(){S('#58585C');L('131ERER313')},function(){S(R='#FF1C22');F('#FFCA57');W(30);c.arc(291,240,69,0,7,0);B()},function(){c.font='105px serif';S(R);c.fillText('\u2605',239,276)}];next=function(i){stages[i]();if(i<6)setTimeout(next,1000,i+1)};next(0)</script>
```
> 17 votes

# Answer
# HTML + CSS, ~~676 636~~ 625 bytes

~~This can be golfed a lot, by getting rid of those `left:XXXpx` and using some sort of centering~~ Now using transforms to center everything instead of `left:XXXpx`.

```
*{left:50%;transform:translate(-50%);position:absolute;border-radius:13px;height:75px}a,b,f{width:145px;background:#404040}b{width:126px;background:#58585C}c{width:163px;height:61px;top:50px}d,e{width:68px;height:40px;top:-15px}c,d,e{background:#1F1A1A}d{left:0;transform:skew(0deg,-26deg);border-radius:9px 24px}e{left:96px;transform:skew(0deg,26deg);border-radius:24px 9px}f{height:40px;width:99px;top:-13px;border-radius:150px/60px}g{height:34px;width:34px;background:#FFCA57;border:5px solid #FF1C22;border-radius:40px;top:13px;color:#FF1C22;font-size:1cm;line-height:31px;padding:3px}
```

```
<c><d></d><e></e><f></f><a><b><g>★
```

*Note: This works best/as expected in Firefox on Windows*

End result looks like:
> 13 votes

# Answer
# ActionScript 3.0, 491 bytes

Golfed form:

```
var h=new Shape(),g=h.graphics,l=g.lineTo,m=g.moveTo,s=g.lineStyle,b=g.beginFill,e=g.endFill,r=g.drawRoundRect;s(23,0x231F20);m(77,18);l(41,36);l(41,73);m(125,18);l(161,36);l(161,73);s();b(0x424143);g.drawEllipse(48,16,106,55);e();b(0x424143);r(38,27,126,65,23,23);e();b(0x595A5C);r(46,27,110,65,17,17);e();s(4.2,0xEC2227);b(0xF9C960);g.drawCircle(101,59,20);e();s();b(0xEC2227);m(106,61);l(115,55);l(104,55);l(101,45);l(98,55);l(87,55);l(96,61);l(93,71);l(101,65);l(110,71);e();addChild(h);

```

Output: http://megaswf.com/file/2708781.swf
> 8 votes

# Answer
# MATLAB R2013a, ~~551~~ 541

This is my first Code Golf. So if anything is not according to the rules, **please teach/tell me** :)

**Golfed form:**

```
hold on
r=[1 .11 .13];h=[];b=2.4;q=-37;o='Curvature';p='Position'
x='FaceColor';z='EdgeColor';v=@rectangle;t=@repmat;s=@set
for i=1:19;h=[h v(p,[-82+b*i -32+i 22 73]) v(p,[60-b*i -32+i 22 73])];end
s(h,o,1,x,[.12 .1 .1])
c=.8:.01:2.2
h=[h fill(104*cos(c),104*sin(c)-52,t(.25,1,3))]
h=[h v(p,[-72 q 144 74],o,.1,x,t(.25,1,3))]
a=v(p,[-63 q 126 74])
a=[a v(p,[-63 q 126 74])]
s(a,o,.1,x,[t(.35,1,2) .36])
v(p,[-20 -20 40 40],o,1,x,[1 .79 .34],z,r,'LineWidth',10)
plot(0,0,'rp',['Marker' x],r,'MarkerSize',58.5)
s([a h],z,'none')
axis equal off

```

**Output** (rasterized):
> 7 votes

# Answer
# LaTeX/TikZ (613 bytes)

```
\RequirePackage{xcolor,tikz}\RequirePackage[active,tightpage]{preview}\PreviewMacro[[!]\tikz\def~#1{\definecolor#1{HTML}}~1{EC2227}~2{F9C960}~3{595A5C}~4{231F20}~5{424143}\def\r{rounded
corners}\def\R{radius}\tikz[x=1pt,y=1pt]{\def~{\fill[}\draw[4,line
width=22.8,line
cap=round,line
join=round](-23.8,41.7)--(-59.9,23.5)--(-59.9,-13.3)--(59.9,-13.3)--(59.9,23.5)--(23.8,41.7);~5,x
\R=53,y
\R=27.4](0,16.4)circle;~5,\r=10.9](-63,-32.65)rectangle(63,32.65);~3,\r=9.5](-55.1,-32.65)rectangle(55.1,32.65);~1,\R=22](0,0)circle;~2,\R=17.8](0,0)circle;~1](90:14.1)\foreach\!in{0,...,4}{--(90+\!*144:14.1)}--cycle;}\stop

```

The result of `pdflatex` is a PDF file with the hat as vector graphics and a tight bounding box.

>

## Ungolfed

```
\documentclass{minimal}
% Package xcolor provides color model HTML
% in order to take the exact same values, used in the SVG file
\usepackage{xcolor}
\usepackage{tikz}

% Package preview is used to get a correct bounding
% box for the graphics
\usepackage[active,tightpage]{preview}
\PreviewEnvironment[{[]}]{tikzpicture}

% Color definitions. one digit instead of a name saves many bytes
\definecolor1{HTML}{EC2227}
\definecolor2{HTML}{F9C960}
\definecolor3{HTML}{595A5C}
\definecolor4{HTML}{231F20}
\definecolor5{HTML}{424143}

\begin{document}
  \begin{tikzpicture}[x=1pt,y=1pt]
    % Draws the dark lines in the background
    \draw[4,line width=22.8,line cap=round,line join=round]
    (-23.8,41.7)--(-59.9,23.5)--(-59.9,-13.3)
    --(59.9,-13.3)--(59.9,23.5)--(23.8,41.7);
    % Draws the ellipsis
    \fill[5,x radius=53,y radius=27.4](0,16.4)circle;
    % Draw the rear rectangle
    \fill[5,rounded corners=10.9](-63,-32.65)rectangle(63,32.65);
    % Draws the rectangle in the foreground
    \fill[3,rounded corners=9.5](-55.1,-32.65)rectangle(55.1,32.65);
    % Draws the red full circle
    \fill[1,radius=22](0,0)circle;
    % Draws the inner yellow circle
    \fill[2,radius=17.8](0,0)circle;
    % Draw the star
    \fill[1](90:14.1)\foreach\!in{0,...,4}{--(90+\!*144:14.1)}--cycle;
  \end{tikzpicture}%
\end{document}

```

The values are taken from the SVG file, they were more accurate (but it also contains rounding errors). The trickiest part was the dark slanted lines in the background. They are drawn as very thick line with rounded line caps and joins.

>
> 6 votes

# Answer
# Perl + TK: 555

The new lines are only for readability, although I got lost of so many variables.

```
use Tk;@w=(-width=>13);$c=tkinit->Canvas->pack;
$c->createPolygon($a=131,$b=163,168,150,$a,$b,$e=269,$b,232,150,$e,$b,$e,$d=225,$a,$d,-outline=>"#1f1a1a",@w);
$c->createPolygon(137,$f=169,263,$f,263,$g=231,137,$g,-outline=>$h="#".40x3,@w);
$c->createOval($a,147,$e,$g,-fill=>$h,-outline=>$h);
$c->createPolygon(143,$f,257,$f,257,$g,143,$g,-fill=>$l="#58585c",-outline=>$l,@w);
$c->createOval(175,175,$d,$d,-width=>5,-fill=>"#ffca57",-outline=>$r="#ff1c22");
$c->createPolygon((map{200+($_%2?17:6)*sin.628*$_,200+($_%2?17:6)*cos.628*$_}0..11),-fill=>$r);
MainLoop

```

Here's a picture:

I don't think it's near pixel perfect, but it's close enough :)
> 1 votes

---
Tags: code-golf, graphical-output, kolmogorov-complexity
---


title: Draw Sri Yantra

text:
# Question
Title: Draw Sri Yantra
## Challenge:

Draw **Sri Yantra**.

## How to:

There are different ways to draw it. All include many steps. If you think you can draw it without following the linked steps scroll below for the **elements you must have in your drawing**.

Complete steps can be found here:

http://www.saralhindi.com/Shri\_Yantra/makingsky14steps\_eng.htm

(*I didn't copied them here because it would become a very long question*, here is archieve.org mirror in case the first link ever goes down)

The final picture should look like the picture below:

## Must have:

Basically any method of drawing of your choosing would be a valid answer providing that you keep the most important elements

1. The number of triangles should the same number as in the above picture (43 smaller triangles resulted from the interlacing of the bigger 9 triangles)
2. This triple intersections are respected:

3. The tips of the upward triangles touch the bases of the 4 downward triangles and the tips of downward triangles should touch the bases of the 3 upward triangles as shown in the figure bellow.
4. The inner circle (bindu) is concentric with the outer circle.
5. The tips (vertices) of the bigger triangles should touch the outer circle:
6. The final image should have all the elements and should generally look like:
7. Color should be roughly the same as the above image for every element (including petals).
8. The shape of the petals should preferably look roughly like in the image bellow, but can also be just semicircles or simple arc section of circle:
9. There are no strict proportion restrictions to the circles or the size of the gates, but the most outer circle should have the diameter not less than 90% of the side of the outer square, the other elements would be respectively arranged relative to this proportions.

## Programming languages and results

There are no restriction to the programming language nor the format of the result (it can be either a vector image, bitmap image, canvas etc) provided that the result is relatively clear and discernible (at least 800px X 800px)

**Latter edit:** There is no perfect method of drawing as this blog so well explores them: http://fotthewuk.livejournal.com/ Taking that into account minor faults will be tolerated.

> At this point it as an interesting exercise to learn that it is very probable that there is no perfect solution, much like squaring of the circle.

# Answer
> 9 votes
# Mathematica - ~~2836~~ 2536 chars

It was a bit dizzying to figure out the combos of regions that make small triangles available for coloring.

## The Frame

The frame objects are inequalities that describe as regions. E.g. the red and yellow scalloping are two regions of circles.

```
n1=8;n2=16;
w8=Round[.78 Table[{Cos[2\[Pi] k/n1],Sin[2\[Pi] k/n1]},{k,0,n1-1}],.01];
w16=Round[1 Table[{Cos[2\[Pi] k/n2],Sin[2\[Pi] k/n2]},{k,0,n2-1}],.01];
n=12;y1=.267;
x2=1/Sqrt[2];w=1.8;v=1.85;
pts={{-w,w},{-w/4,w},{-w/4,w+w/8},{-5w/8,w+w/8},{-5w/8,w+5w/24},{5w/8,w+5w/24},{5w/8,w+w/8},{w/4,w+w/8},{w/4,w},
{w,w},{w,w/4},{w+w/8,w/4},{w+w/8,5w/8},{w+5w/24,5w/8},{w+5w/24,-5w/8},{w+w/8,-5w/8},{w+w/8,-w/4},{w,-w/4},
{w,-w},
{w/4,-w},{w/4,-w-w/8},{(5 w)/8,-w-w/8},{(5 w)/8,-w-(5 w)/24},{-((5 w)/8),-w-(5 w)/24},{-((5 w)/8),-w-w/8},{-(w/4),-w-w/8},{-(w/4),-w},{-w,-w},

{-w,-w/4},{-w-w/8,-w/4},{-w-w/8,-5w/8},{-w-5w/24,-5w/8},{-w-5w/24,5w/8},{-w-w/8,5w/8},{-w-w/8,w/4},{-w,w/4}
};

frame=RegionPlot[{
(*MeshRegion[pts2,Polygon[Range[20]]],*) (*orange trim *)
MeshRegion[pts,Polygon[Range[Length[pts]]]], (*green box *)
ImplicitRegion[x^2+y^2<2.8,{x,y}], (*white, largest circle *)
ImplicitRegion[Or@@(((x-#)^2+(y-#2)^2<.1)&@@@w16),{x,y}], (*yellow scallops*)
ImplicitRegion[x^2+y^2<1,{x,y}],(*white circle *)
ImplicitRegion[x^2+y^2<1.4,{x,y}],(*white disk*)
ImplicitRegion[Or@@(((x-#)^2+(y-#2)^2<.15)&@@@w8),{x,y}],(*red scallops*)
ImplicitRegion[x^2+y^2<1,{x,y}] , (*white disk *)
ImplicitRegion[1.8 < x^2+y^2< 2.2,{x,y}] ,(*brown outer rim*)
ImplicitRegion[2.4 < x^2+y^2< 2.8,{x,y}](*yellow outer rim*)},
BoundaryStyle->Directive[Thickness[.005],Black],
AspectRatio->1,
Frame-> False,
PlotStyle->{(*Lighter@Orange,*)
Darker@Green,White,Yellow,White,White,
Red,White,Lighter@Brown,Yellow,Red,
White,White,White,White,White,
White,White,Red,Red,Darker@Blue,
Darker@Blue,Darker@Blue,Darker@Blue,Darker@Blue,Darker@Blue,
Red,Red,Darker@Blue,Red,Yellow,Red}];

```

Then there is a disk to hide some circles that were used to make the scalloping.

```
Graphics[{White,Disk[{0,0},.99]}]

```

---

## The Innards

Some definitions of vertices and triangles. Each triangle, t1, t2,... is a distinct region. Logical operations (`RegionUnion`. `RegionIntersection`, and `RegionDifference`) on large triangles are used to define smaller, triangular cells as derived regions that can be individually colored.

```
p1={-Cos[ArcTan[.267]],y1};
p2={Cos[ArcTan[.267]],y1};
p3={-Cos[ArcTan[.267]],-y1};
p4={Cos[ArcTan[.267]],-y1};
p5={-x2,(x2+y1)/2};
p6={x2,(x2+y1)/2};
p7={-x2,-(x2+y1)/2};
p8={x2,-(x2+y1)/2};
p9={0.5,-x2};
p10={-0.5,-x2};
p11={0.5,-x2};
p12={-0.5,-x2};
p13={a=-.34,b=-.12};
p14={-a,b};
p15={0.5,x2};
p16={-0.5,x2};
t1=MeshRegion[{{0,-1},p1,p2},Triangle[{1,2,3}]];
t2=MeshRegion[{{0,1},p3,p4},Triangle[{1,3,2}]];
t3=MeshRegion[{{0,-x2},p5,p6},Triangle[{1,3,2}]];
t4=MeshRegion[{{0,x2},p7,p8},Triangle[{1,3,2}]];
t5=MeshRegion[{{0,+y1},p9,p10},Triangle[{1,3,2}]];
t6=MeshRegion[{{0,p5[[2]]},p13,p14},Triangle[{1,3,2}]];
t7=MeshRegion[{{0,p13[[2]]},p15,p16},Triangle[{1,3,2}]];
t8=MeshRegion[{{0,p7[[2]]},{-.33,p1[[2]]-.12},{.33,p1[[2]]-.12}},Triangle[{1,3,2}]];
t9=MeshRegion[{{0,p3[[2]]},{z=-.23,0.063},{-z,.063}},Triangle[{1,3,2}]];

```

---

```
disk=Graphics[{White,Disk[{0,0},.99]}];

innards=RegionPlot[{
t1,t2,t3,t4,t5,t6,t7,t8,t9,(*White*)
RegionDifference[t1,RegionUnion[t5,t4,t2]],(*Blue*)
RegionDifference[t4,RegionUnion[t1,t3,t5]],(*red*)
RegionDifference[t3,RegionUnion[t7,t4,t2]], (*blue*)
RegionDifference[t2,RegionUnion[t1,t7,t3]], (*blue*)
RegionDifference[t5,t1],   (*blue*)
RegionDifference[t4,RegionUnion[t1,t7]], (*Blue *)
RegionDifference[t7,t2],(*Blue*)
RegionDifference[t3,RegionUnion[t1,t2]],(*Blue *)
RegionDifference[t8,t2],  (* blue *)
RegionDifference[t9,t5],  (* red *)
RegionDifference[t9,t6],  (* red *)
RegionIntersection[t4,RegionDifference[t6,t1]], (*blue*)
RegionIntersection[t6,RegionDifference[t5,t8]],  (* red *)
RegionIntersection[t7,t9], (*yellow*)
RegionDifference[RegionIntersection[t7,t8],t5], (*red *)
RegionDifference[RegionIntersection[t5,t6],RegionUnion[t7,t9]],(*red *)
ImplicitRegion[x^2+y^2<= .001,{x,y}],  (* smallest circle *) (* red *)
RegionDifference[RegionIntersection[t7,t1 ],t6], (*Red*)
RegionDifference[t8,RegionUnion[t5,t6]],
RegionDifference[t6,RegionUnion[t7,t8]],
RegionDifference[RegionIntersection[t2,t5],RegionUnion[t7,t8]],
RegionDifference[RegionIntersection[t7,t3],t4],
RegionDifference[RegionIntersection[t1,t3],RegionUnion[t5,t4]],
RegionDifference[RegionIntersection[t2,t4],RegionUnion[t7,t3]],
RegionDifference[RegionIntersection[t5,t4],t3]},
BoundaryStyle->Directive[Thickness[.005],Black],
AspectRatio->1,
PlotStyle->{
White,White,White,White,White,White,White,White,White,
Blue,Red,Red,Blue,Blue,Blue,Blue,Blue,Blue,
Red,Red,Blue,Red,Yellow,Red,Red,Red,Blue,Blue,Blue,Blue,Red,Red,Red,Red}]

```

---

## Putting the parts together

```
Show[frame,disk,innards,Graphics[{Brown,Thickness[.02],Line[Append[pts,{-w,w}]]}];
Graphics[{RGBColor[0.92,0.8,0.],Thickness[.015],Line[Append[pts,{-w,w}]]}]]

```

---

## Golfed

```
r=ImplicitRegion;m=MeshRegion;t=Triangle;d=RegionDifference;u=RegionUnion;i=RegionIntersection;(*s=ImplicitRegion*)

n1=8;n2=16;w8=.78 Table[{Cos[2\[Pi] k/n1],Sin[2\[Pi] k/n1]},{k,0,n1-1}];
w16=Table[{Cos[2\[Pi] k/n2],Sin[2\[Pi] k/n2]},{k,0,n2-1}];n=12;y1=.267;x2=1/Sqrt[2];w=1.8;v=1.85;
pts={{-w,w},{-w/4,w},{-w/4,w+w/8},{-5w/8,w+w/8},{-5w/8,w+5w/24},{5w/8,w+5w/24},{5w/8,w+w/8},{w/4,w+w/8},{w/4,w},
{w,w},{w,w/4},{w+w/8,w/4},{w+w/8,5w/8},{w+5w/24,5w/8},{w+5w/24,-5w/8},{w+w/8,-5w/8},{w+w/8,-w/4},{w,-w/4},
{w,-w},{w/4,-w},{w/4,-w-w/8},{(5 w)/8,-w-w/8},{(5 w)/8,-w-(5 w)/24},{-((5 w)/8),-w-(5 w)/24},{-((5 w)/8),-w-w/8},{-(w/4),-w-w/8},{-(w/4),-w},{-w,-w},
{-w,-w/4},{-w-w/8,-w/4},{-w-w/8,-5w/8},{-w-5w/24,-5w/8},{-w-5w/24,5w/8},{-w-w/8,5w/8},{-w-w/8,w/4},{-w,w/4}};

frame=RegionPlot[{
m[pts,Polygon[Range[Length[pts]]]],
r[x^2+y^2<2.8,{x,y}],
r[Or@@(((x-#)^2+(y-#2)^2<.1)&@@@w16),{x,y}],
r[x^2+y^2<1,{x,y}],
r[x^2+y^2<1.4,{x,y}],
r[Or@@(((x-#)^2+(y-#2)^2<.15)&@@@w8),{x,y}],
r[x^2+y^2<1,{x,y}] ,
r[1.8 < x^2+y^2< 2.2,{x,y}] ,
r[2.4 < x^2+y^2< 2.8,{x,y}]},
BoundaryStyle->Directive[Thickness[.003],Black],
AspectRatio->1,
Frame-> False,
PlotStyle->{Darker@Green,White,Yellow,White,White,Red,White,Lighter@Brown,Yellow,Red}];

c=Cos[ArcTan[y1]];
p1={-c,y1};
p2={c,y1};
p3={-c,-y1};
p4={c,-y1};
p5={-x2,(x2+y1)/2};
p6={x2,(x2+y1)/2};
p7={-x2,-(x2+y1)/2};
p8={x2,-(x2+y1)/2};
p9={0.5,-x2};
p10={-0.5,-x2};
p11={0.5,-x2};
p12={-0.5,-x2};
p13={a=-.34,b=-.12};
p14={-a,b};
p15={0.5,x2};
p16={-0.5,x2};
t1=m[{{0,-1},p1,p2},t[{1,2,3}]];
t2=m[{{0,1},p3,p4},t[{1,3,2}]];
t3=m[{{0,-x2},p5,p6},t[{1,3,2}]];
t4=m[{{0,x2},p7,p8},t[{1,3,2}]];
t5=m[{{0,+y1},p9,p10},t[{1,3,2}]];
t6=m[{{0,p5[[2]]},p13,p14},t[{1,3,2}]];
t7=m[{{0,p13[[2]]},p15,p16},t[{1,3,2}]];
t8=m[{{0,p7[[2]]},{-.33,p1[[2]]-.12},{.33,p1[[2]]-.12}},t[{1,3,2}]];
t9=m[{{0,p3[[2]]},{z=-.23,0.063},{-z,.063}},t[{1,3,2}]];

innards=RegionPlot[{
d[t1,u[t5,t4,t2]],
d[t4,u[t1,t3,t5]],
d[t3,u[t7,t4,t2]],
d[t2,u[t1,t7,t3]],
d[t5,t1],
d[t4,u[t1,t7]],
d[t7,t2],
d[t3,u[t1,t2]],
d[t8,t2],
d[t9,t5],
d[t9,t6],
i[t4,d[t6,t1]],
i[t6,d[t5,t8]],
i[t7,t9],
d[i[t7,t8],t5],
d[i[t5,t6],u[t7,t9]],
r[x^2+y^2<= .001,{x,y}],
d[i[t7,t1 ],t6],
d[t8,u[t5,t6]],
d[t6,u[t7,t8]],
d[i[t2,t5],u[t7,t8]],
d[i[t7,t3],t4],
d[i[t1,t3],u[t5,t4]],
d[i[t2,t4],u[t7,t3]],
d[i[t5,t4],t3]},
BoundaryStyle->Directive[Thickness[.003],Black],
Frame->False,
PlotStyle->{Blue,Red,Red,Blue,Blue,Blue,Blue,Blue,Blue,
Red,Red,Blue,Red,Yellow,Red,Red,Red,Blue,Blue,Blue,Blue,Red,Red,Red,Red}];

trim=Graphics[{RGBColor[0.92,0.8,0.],Thickness[.01],Line[Append[pts,{-w,w}]]}];
trim2=Graphics[{Brown,Thickness[.02],Line[Append[pts,{-w,w}]]}];
Show[frame,Graphics[{White,Disk[{0,0},.99]}],trim2,trim,innards]

```

---
Tags: code-golf, graphical-output
---


title: Sharing pizza fairly

text:
# Question
Title: Sharing pizza fairly
The difficulty with sharing pizza with friends is that it is hard to make sure that everyone gets the same amount of pepperoni on their slice. So, your task is to decide how to fairly slice a pizza so that everyone is happy.

## Directions

Write a program that, given a list of the positions of pepperonis on a circular pizza and the number of slices to be made, outputs a list of the angles that the pizza should be cut at so that each slice has the same amount of pepperoni on it.

* The pizza has only one topping: pepperoni.
* Your friends don't care about the size of their slice, just that they are not cheated out of any pepperoni.
* The pizza is a circle centered on the origin `(0, 0)` and with a **radius of `1`**.
* The pepperonis are circles that are centered wherever the input says they are centered and have a **radius of `0.1`**
* Take input as an **integer** that represents the number of slices to be made and a **list of ordered-pairs** that represent the positions of the pepperonis on a cartesian coordinate system. (In any reasonable format)
* Output should be a list of angles given in **radians** that represents the positions of the "cuts" to the pizza (in the **range `0 <= a < 2pi`**). (In any reasonable format) (Precision should be to at least `+/- 1e-5`.)
* **You can have partial pieces of a pepperoni on a slice** (eg. If a pizza has one pepperoni on it and it needs to be shared by 10 people, cut the pizza ten times, all cuts slicing through the pepperoni. But make sure it's fair!)
* A cut can (may have to) slice through multiple pepperonis.
* Pepperonis may overlap.

## Examples

**Input:**

```
8 people, pepperonis: (0.4, 0.2), (-0.3, 0.1), (-0.022, -0.5), (0.3, -0.32)

```

**Possible valid output:**

```
slices at:
0, 0.46365, 0.68916, 2.81984, 3.14159, 4.66842, 4.86957, 5.46554

```

Here is a visualisation of this example (everyone gets half a pepperoni):

More examples:

```
Input: 9 people, 1 pepperoni at: (0.03, 0.01)
Output: 0, 0.4065, 0.8222, 1.29988, 1.94749, 3.03869, 4.42503, 5.28428, 5.83985

```

```
Input: 5, (0.4, 0.3), (0.45, 0.43), (-0.5, -0.04)
Output: 0, 0.64751, 0.73928, 0.84206, 3.18997

```

## Scoring

This is , so least number of bytes wins.

# Answer
# Mathematica, 221 bytes

```
f=(A=Pi.01Length@#2/#;l=m/.Solve[Norm[{a,b}-m{Cos@t,Sin@t}]==.1,m];k=(l/.{a->#,b->#2})&@@@#2;d=1.*^-5;For[Print[h=B=0];n=1,n<#,h+=d,(B+=If[Im@#<0,0,d(Max[#2,0]^2-Max[#,0]^2)/2])&@@@(k/.{t->h});If[B>A,n+=1;Print@h;B-=A]])&

```

Ungolfed:

```
f = (
   A = Pi .01 Length@#2/#;
   l = m /. Solve[Norm[{a, b} - m {Cos@t, Sin@t}] == .1, m];
   k = (l /. {a -> #, b -> #2}) & @@@ #2;
   d = 1.*^-5;
   For[Print[h = B = 0]; n = 1, n < #, h += d,
    (
      B += If[Im@# < 0, 0, d (Max[#2, 0]^2 - Max[#, 0]^2)/2]
    ) & @@@ (k /. {t -> h});
    If[B > A, n += 1; Print@h; B -= A]
   ]
) &

```

This defines a function which takes as parameters the number of slices and a list of pairs for the peperoni coordinates, like

```
f[8, {{0.4, 0.2}, {-0.3, 0.1}, {-0.022, -0.5}, {0.3, -0.32}}]

```

It will print the slices to the console as it traverses the pizza.

On most pizzas, this is fairly slow, because (to achieve the required precision) I'm integrating the peperoni area from 0 to 2π in steps of 1e-5. To get a slightly less precise result in a reasonable amount of time, you can change the `1.*^-5` at the end to `1.*^-3`.

## How it works

The idea is to sweep out the slices of pizza while integrating over the area of the peperoni pieces covered. Whenever that area hits the required amount of peperoni per person, we report the current angle and reset the area counter.

To obtain the peperoni area swept out, we intersect the line with the peperoni to give use the two distances from the origin, where the line intersects with the peperoni. Since a line extends to infinity in both directions, we need to clamp these distances to non-negative values. This solves two problems:

* Counting intersections with each peperoni twice, once positive and once negative (which would actually yield to an overall area of 0).
* Counting only wedges of peperoni pieces which include in the origin.

I'll include some diagrams later.
> 7 votes

---
Tags: code-golf, math, geometry
---


title: Rand5() to Rand7()

text:
# Question
Title: Rand5() to Rand7()
You are provided with a function Rand5(). This function returns perfectly random (equal distribution) integers between 1 and 5.

Provide the function Rand7(), which uses Rand5() to produce perfectly random integers between 1 and 7.

# Answer
Java - 61 chars

```
int rand7(){int s=0,c=7;while(c-->0)s+=rand5();return s%7+1;}

```

Test driver for validation:

```
class Rand {

    public static void main(String[] args) {
        int[] nums = new int[7];
        // get a lot of numbers
        for(int i = 0; i < 10000000; i++) nums[rand7()-1]++;
        // print the results
        for(int i = 0; i < 7; i++) System.out.println((i+1) + ": " + nums[i]);
    }

    // just for rand5()
    static java.util.Random r = new java.util.Random();

    static int rand5() {
        return r.nextInt(5)+1; // Random.nextInt(n) returns 0..n-1, so add 1
    }

    static int rand7(){int s=0,c=7;while(c-->0)s+=rand5();return s%7+1;}

}

```

Results

```
C:\Documents and Settings\glowcoder\My Documents>java Rand
1: 1429828
2: 1429347
3: 1428328
4: 1426486
5: 1426784
6: 1429853
7: 1429374

C:\Documents and Settings\glowcoder\My Documents>

```
> 12 votes

# Answer
## Perl - 47 (was 52) chars

```
sub rand7{($x=5*&rand5+&rand5-3)<24?int($x/3):&rand7}

```

Plus I get to use the ternary operator AND recursion. Best... day... ever!

OK, 47 chars if you use mod instead of div:

```
sub rand7{($x=5*&rand5+&rand5)<27?$x%7+1:&rand7}

```
> 8 votes

# Answer
In Python:

```
def Rand7():
  while True:
    x = (Rand5() - 1) * 5 + (Rand5() - 1)
    if x < 21: return x/3 + 1

```
> 7 votes

# Answer
## JavaScript, 42

```
Rand7=f=_=>(x=Rand5()+Rand5()*5-5)>7?f():x

```

Bonus ES5 thing:

```
Rand7=eval.bind(0,'for(;x=Rand5()+Rand5()*5-5,x>7;);x')

```
> 7 votes

# Answer
Ruby - 54 chars (based on Dan McGrath solution, using loop)

```
def rand7;x=8;while x>7 do x=rand5+5*rand5-5 end;x;end

```

Ruby - 45 chars (same solution, using recursion)

```
def rand7;x=rand5+5*rand5-5;x>7 ?rand7: x;end

```
> 7 votes

# Answer
In Common Lisp 70 characters:

```
(defun rand7()(let((n(-(+(rand5)(* 5(rand5)))5)))(if(> n 7)(rand7)n)))

```

The parenthesis take up more space than I would like.
> 5 votes

# Answer
In c/c++ using rejection sampling

```
int rand7(){int x=8;while(x>7)x=rand5()+5*rand5()-5;return x;}

```

62 characters.
> 4 votes

# Answer
Translation to PHP, from the answer posted ny Dan McGrath.

```
function Rand7(){$x=8;while($x>7)$x=rand5()+5*rand5()-5;return $x;}

```

67 characters.
> 4 votes

# Answer
# R, 34 characters

In R (a language built for statistical computation), a deliberately cheaterish solution:

```
# Construct a Rand5 function
Rand5 <- function() sample(seq(5),1)
# And the golf
Rand7=function(r=Rand5())sample(1:(r/r+6),1)
# Or (same character count)
Rand7=function(r=Rand5())sample.int(r/r+6,1)
# Or even shorter(thanks to @Spacedman)
Rand7=function()sample(7)[Rand5()]

```

Thanks to lazy evaluation of arguments, I eliminated the semicolon and braces.

Output over 10^6 replicates:

```
> test <- replicate(10^6,Rand7())
> table(test)
test
     1      2      3      4      5      6      7
142987 142547 143133 142719 142897 142869 142848

library(ggplot2)
qplot(test)

```
> 4 votes

# Answer
In Java (or C/C++ I suppose)

* using generation formula by Alexandru, in 65 characters:

```
int rand7(){int x=rand5()*5+rand5()-6;return x>20?rand7():x/3+1;}

```
* using generation formula by Dan McGrath, in 60 characters

```
int rand7(){int x=rand5()+5*rand5()-5;return x>7?rand7():x;}

```
> 3 votes

# Answer
## C++

```
int Rand4()
{
    int r = Rand5();
    return r > 4 ? Rand4() : r;
}

inline int Rand8()
{
    return (Rand4() - 1) << 2 + Rand4();
}

int Rand7()
{
    int r = Rand8();
    return r > 7 ? Rand7() : r;
}

```

---

## C++ (109)

### Golfed

```
int Rand4(){int r=Rand5();return r>4?Rand4():r;}int Rand7(){int r=Rand4()-1<<2+Rand4();return r>7?Rand7():r;}

```
> 3 votes

# Answer
## scala,  47, 40 59 chars:

```
def rand7:Int={val r=5*(rand5-1)+rand5
if(r<8)r else rand7}

```

with 2 inputs from rand5:

```
\ 1 2 3 4 5
1 1 2 3 4 5
2 6 7 8 ..
3 11 ..
4 ..
5

```

I multiply the first-1 by 5, and add the second. Most results are ignored, and lead to a new calculation. The result should be an equal distribution of values from 1-25, from which I only pick the first 7 ones. I could accept the first 21 with building a modulo, but this would lead to longer code.

historic code which failed, but not very obviously. Thanks to Ilmari Karonen for pointing it out:

```
def rand7=(1 to 7).map(_=>rand5).sum%7+1

```

Thanks to Yoshiteru Takeshita, for this scala-2.8.0-approach which made 'sum' so easy. My solution before:

```
def rand7=((0/:(1 to 7))((a,_)=>a+rand5-1))%7+1

```

rand5:

```
val rnd = util.Random
def rand5 = rnd.nextInt (5) + 1

```
> 3 votes

# Answer
## С++

```
int Rand7()
{
    int r = Rand5();
    int n = 5;
    do {
        r = (r - 1) * 5 + Rand5();
        int m = n * 5 / 7 * 7;
        if (r <= m) {
            return r % 7 + 1;
        }
        r -= m;
        n = n * 5 - m;
    } while (1);
}

```

Numbers distribution (1000000 integers):

```
142935 142751 142652 143299 142969 142691 142703

```

Average number of calls to Rand5() per every generated integer is about 2.2 (2 to 10+).

```
1 2      3      4     5    6   7 8  9 10
0 840180 112222 44433 2212 886 0 60 6 1

```
> 3 votes

# Answer
Translation to Javascript, from the answer posted by Dan McGrath.

```
function Rand7(){x=8;while(x>7)x=rand5()+5*rand5()-5;return x}

```

**62 chars**
> 2 votes

# Answer
# Python, 56 37 chars

Another solution that may be wrong, in Python:

```
rand7 = lambda: sum(rand5() for i in range(7)) % 7 + 1

```

This seems to be too simple, but when I try:

```
counter = [0] * 7
for i in range(100000):
     counter[rand7()] += 1

```

I get a reasonably even distribution (all between 14000 and 14500).

Okay, now as somebody voted for this post: Is this solution indeed correct? I more posted this here to make people criticize it. Well, if it is correct, my golfed version would be:

```
rand7=lambda:eval("+rand5()"*7)%7+1

```

which comes out to 37 chars.
> 2 votes

# Answer
## JavaScript, 85

```
function Rand7(){for(x=0,i=1;i<8;x^=i*((k=Rand5())%2),i*=1+(k<5));return x?x:Rand7()}

```

I know there's shorter answer, but I wanted to show the test of this puzzle. It turns out that only Clyde Lobo's answer using Dan McGrath's rejection sampling is correct (between JS answers).
> 2 votes

# Answer
Java, 65 chars:

```
int rand7(){int r;do{r=rand5()+5*rand5()-5;}while(r>7);return r;}

```
> 2 votes

# Answer
## Java - 66 chars

```
int rand7(){int s;while((s=rand5()*5+rand5())<10);return(s%7+1);}

```

Longer than previous routine, but I think this one returns uniformly distributed numbers in less time.
> 2 votes

# Answer
# Clojure - 58 chars

```
(defn rand7[](#(if(<% 8)%(rand7))(+(rand5)(*(rand5)5)-5)))

```
> 1 votes

# Answer
# Python, 70 chars

```
def rand7():
 while True:
  n=5*(rand5()-1)+(rand5()-1)
  if n<21:return n%7+1

```

but completely correct based on the reasoning here.
> 1 votes

# Answer
## Perl, 43 chars, iterative rejection sampling

```
sub rand7{1while($_=5*&rand5-rand5)>6;$_+1}

```

This gives a warning about `Ambiguous use of -rand5 resolved as -&rand5()`, but works correctly. Prepending an `&` also to the second `rand5` call fixes it at the cost of one stroke. (Conversely, the other `&` can also be removed *if* `rand5` has been defined with a `()` prototype.)

Ps. The following 46-char version is about three times faster:

```
sub rand7{1while($_=5*&rand5-rand5)>20;$_%7+1}

```
> 1 votes

# Answer
**PostScript (46)**

This uses binary token encoding, therefore, here is a hexdump:

```
00000000  2f 72 61 6e 64 37 7b 38  7b 92 38 37 92 61 7b 92  |/rand7{8{.87.a{.|
00000010  40 7d 69 66 92 75 32 7b  72 61 6e 64 35 7d 92 83  |@}if.u2{rand5}..|
00000020  35 92 6c 92 01 35 92 a9  7d 92 65 7d 92 33        |5.l..5..}.e}.3|
0000002e

```

To try it out, you can also download it.

Here is the ungolfed and commented code, together with testing code.

```
% This is the actual rand7 procedure.
/rand7{
  8{                      % potentialResult
    % only if the random number is less than or equal to 7, we're done
    dup 7 le{             % result
      exit                % result
    }if                   % potentialResult
    pop                   % -/-
    2{rand5}repeat        % randomNumber1 randomNumber2
    5 mul add 5 sub       % randomNumber1 + 5*randomNumber2 - 5 = potentialResult
  }loop
}def

%Now, some testing code.

% For testing, we use the built-in rand operator;
% Doesn't really give a 100% even distribution as it returns numbers
% from 0 to 2^31-1, which is of course not divisible by 5.
/rand5 {
  rand 5 mod 1 add
}def

% For testing, we initialize a dict that counts the number of times any number
% has been returned. Of course, we start the count at 0 for every number.
<<1 1 7{0}for>>begin

% Now we're calling the function quite a number of times
% and increment the counters accordingly.
1000000 {
  rand7 dup load 1 add def
}repeat

% Print the results
currentdict{
  2 array astore ==
}forall

```
> 1 votes

# Answer
```
int result = 0;

for (int i = 0; i++; i<7)
    if (((rand(5) + rand(5)) % 2) //check if odd
        result += 1;

return result + 1;

```
> 0 votes

# Answer
# R (30 characters)

Define rand7:

```
rand7=function(n)sample(7,n,T)

```

Because R was written with statistical analysis in mind, this task is trivial, and I use the built-in function `sample` with replacement set to TRUE.

Sample output:

```
> rand7(20)
 [1] 4 3 6 1 2 4 3 2 3 2 5 1 4 6 4 2 4 6 6 1
> rand7(20)
 [1] 1 2 5 2 6 4 6 1 7 1 1 3 7 6 4 7 4 2 1 2
> rand7(20)
 [1] 6 7 1 3 3 1 5 4 3 4 2 1 5 4 4 4 7 7 1 5

```
> 0 votes

# Answer
# Groovy

```
rand7={if(b==null)b=rand5();(b=(rand5()+b)%7+1)}

```

example distribution over 35,000 iterations:

```
[1:5030, 2:4909, 3:5017, 4:4942, 5:5118, 6:4956, 7:5028]

```

Is it bad that it's stateful?
> 0 votes

# Answer
## Mathematica, 30

```
Rand7=Rand5[]~Sum~{7}~Mod~7+1&

```
> 0 votes

# Answer
How about this?

```
int Rand7()
{
    return Rand5()+ Rand5()/2;
}

```
> 0 votes

# Answer
# Ruby (43 bytes)

```
def rand7;(0..7).reduce{|i|i+rand5}%7+1;end

```

cemper93's solution ported to Ruby is three bytes shorter ;) (34 bytes)

```
def rand7;eval("+rand5"*7)%7+1;end

```
> 0 votes

# Answer
## Java - 54

```
int m=0;int rand7(){return(m=m*5&-1>>>1|rand5())%7+1;}

```

Distribution test: `[1000915, 999689, 999169, 998227, 1001653, 1000419, 999928]`

Algorithm:

* Keep a global variable
* multiply by 5, so there get 5 places free at the least significant end
* Truncate the sign bit to make it positive (not necessary if unsigned numbers were supported)
* Modulo 7 is the answer

\> The numbers are not mutually uncorrelated anymore, but individually perfectly random.
> -1 votes

# Answer
**C/C++ code** the core code has one line only!

```
static unsigned int gi = 0;

int rand7()
{
    return (((rand() % 5 + 1) + (gi++ % 7)) % 7) + 1;
}

//call this seed before rand7
//maybe it's not best seed, if yo have any good idea tell me please
//and thanks JiminP again, he remind me to do this
void srand7()
{
    int i, n = time(0);
    for (i = 0; i < n % 7; i++)
        rand7();
}

```

The srand7() is the seed of rand7, must call this function before rand7, just like call srand before rand in C.

This is a very good one, because it call rand() only one time, and no loop thing, no expends extra memories.

Let me explain it: consider a integer array with size of 5:

```
1st get one number from 1 2 3 4 5 by rand5
2nd get one number from 2 3 4 5 6
3rd get one number from 3 4 5 6 7
4th get one number from 4 5 6 7 1
5th get one number from 5 6 7 1 2
5th get one number from 6 7 1 2 3
7th get one number from 7 1 2 3 4

```

So we got the TABLE, each one of 1-7 appears 5 times in it, and has all 35 numbers, so the probability of each number is 5/35=1/7. And next time,

```
8th get one number from 1 2 3 4 5
9th get one number from 2 3 4 5 6
......

```

After enough times, we can get the uniform distribution of 1-7.

So, we can allocate a array to restore the five elements of 1-7 by loop-left-shift, and get one number from array each time by rand5. Instead, we can generate the all seven arrays before, and using them circularly. The code is simple also, has many short codes can do this.

But, we can using the properties of % operation, so the table 1-7 rows is equivalent with (rand5 + i) % 7, that is : a = rand() % 5 + 1 is rand5 in C language, b = gi++ % 7 generates all permutations in table above, and 0 - 6 replace 1 - 7 c = (a + b) % 7 + 1, generates 1 - 7 uniformly. Finally, we got this code:

```
(((rand() % 5 + 1) + (gi++ % 7)) % 7) + 1

```

But, we can not get 6 and 7 at first call, so we need a seed, some like srand for rand in C/C++, to disarrange the permutation for first formal call.

Here is the full code to testing:

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static unsigned int gi = 0;

//a = rand() % 5 + 1 is rand5 in C language,
//b = gi++ % 7 generates all permutations,
//c = (a + b) % 7 + 1, generates 1 - 7 uniformly.
//Dont forget call srand7 before rand7
int rand7()
{
   return (((rand() % 5 + 1) + (gi++ % 7)) % 7) + 1;
}

//call this seed before rand7
//maybe it's not best seed, if yo have any good idea tell me please
//and thanks JiminP again, he remind me to do this
void srand7()
{
    int i, n = time(0);
    for (i = 0; i < n % 7; i++)
        rand7();
}

void main(void)
{
    unsigned int result[10] = {0};
    int k;

    srand((unsigned int)time(0)); //initialize the seed for rand
    srand7() //initialize the rand7

    for (k = 0; k < 100000; k++)
        result[rand7() - 1]++;

    for (k = 0; k < 7; k++)
        printf("%d : %.05f\n", k + 1, (float)result[k]/100000);
}

```
> -2 votes

# Answer
### JavaScript (53 characters):

```
function Rand7(){return Math.abs(Rand5()-3)+Rand5()}

```

JSFiddle Example: here

Same algorithm on **PHP (49 characters):**

```
function Rand7(){return abs(Rand5()-3)+Rand5();}

```
> -3 votes

---
Tags: code-challenge, math, random
---


# Question
Title: Change the innermost element type of a jagged array — any .NET language: C#, F#, VB.NET, MSIL, C++/CLI, etc
Write a class containing a method with the signature

```
System.Array ChangeElementType(System.Array jaggedArray)

```

(you may rename identifiers `ChangeElementType`, `jaggedArray` and shorten the type `System.Array` with `using` directives). The class may contain any additional members if needed.

You may assume the following preconditions (and do not need to validate them):

* The argument `jaggedArray` is not `null`.
* The argument `jaggedArray` is an array instance whose type can be represented in C# notation as `int[...]...`, i.e. the type `int` followed by 1 or more rank specifiers `[...]` where each rank specifier is a pair or square brackets with 0 or more commas between them. For example, it could be an array of type `int[]`, `int[,][][,,,]`, etc.
* No element at any level of the `jaggedArray` is `null`.
* All elements at any level of the `jaggedArray` are distinct w.r.t. reference equality (i.e. the same array instance does not appear at several different positions).
* The lower bound of any array dimension is 0.
* The length of any dimension and the total number of elements of any array fits into the type `int`.

The method must create and return an array of type `long[...]...` which is obtained from the type of `jaggedArray` by replacing `int` with `long` and keeping all rank specifiers the same. The result must have the same shape as `jaggedArray`, i.e. all array dimensions at any level must be the same. All elements at the innermost level must have the same numeric values (cast from `int` to `long`). The method must not mutate the argument `jaggedArray` or any its elements at any level.

The solution may be implemented in any language for the .NET platform: C#, F#, VB.NET, MSIL, C++/CLI, etc. All necessary `using`, `open` or `imports` directives or fully qualified names must be explicitly specified (do not rely on IDE defaults). The only referenced assembly must be `mscorlib`, no P/Invoke or COM Interop allowed. The solution cannot access any Internet services to get the result, intermediate data or to download parts of an algorithm.

It is a golf — try to minimize the number of bytes in the source.

# Answer
# C# - 396 ~~440~~ ~~595~~

I'm not entirely sure why I did this, and I can't help but feel I'm missing something. Rewrote the old `c` (for copy) method as a for-loop in the ChangeElementType method (`f`). Unless I find something substantial, I think I'll not be making this any shorter.

Golfed code:

```
using A=System.Array;using T=System.Type;class P{T g(T o){return o.IsArray?g(o.GetElementType()).MakeArrayType(o.GetArrayRank()):typeof(long);}A f(A a){var R=a;int i,r;for(var x=new int[i=r=a.Rank];;){if(i<1){if(a!=R)return R;R=A.CreateInstance(g(a.GetType().GetElementType()),x);i=1;}if(--i<r)if(x[i]-->0)i+=2;else x[i]=a.GetLength(i);else{var o=a.GetValue(x);R.SetValue(o is A?f((A)o):o,x);}}}}

```

Readable code with an excuse for a test:

```
using A=System.Array;
using T=System.Type;

class P
{
    // turns a type like "int[,][]" into "long[,][]"
    T g(T o)
    {
        return o.IsArray?g(o.GetElementType()).MakeArrayType(o.GetArrayRank()):typeof(long);
    }

    // ChangeElementType
    A f(A a)
    {
        var R=a; // R is the result, a gives us the type and a nice default value
        int i,r; // i is a counter, r is the rank

        // this loop first counts backwards filling the x array with the dimension lengths
        // then it does a tree traversal and copies things about
        for(var x=new int[i=r=a.Rank];;) // create the x array, and sets i and r
        {
            if(i<1)
            { // gone off start
                if(a!=R) // been here before
                    return R; // return the result
                R=A.CreateInstance(g(a.GetType().GetElementType()),x); // create the array to fill
                i=1; // move to start of x
            }

            if(--i<r) // move back
                if(x[i]-->0) // decrement index
                    i+=2; // move forward instead
                else
                    x[i]=a.GetLength(i); // reset index
            else
            {
                var o=a.GetValue(x); // get the int/array
                R.SetValue(o is A?f((A)o):o,x); // if it's an array, Change it, if not, pass it directly (the int)
            }
        }
    }

    // test method (prints True if the code works, might print False if it doesn't)
    static void Main()
    {
        string old = "";

        var a = new int[10][,];

        for (int i = 0; i < 10; i++)
        {
            a[i] = new int[3,5];

            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 5; k++)
                {
                    int v = i * j * k;
                    a[i][j,k] = v;
                    old += v.ToString();
                }
            }
        }

        long[][,] l = (long[][,])(new P().f(a));

        string nwe = "";

        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                for (int k = 0; k < 5; k++)
                {
                    nwe += l[i][j,k].ToString();
                }
            }
        }

        System.Console.WriteLine(old == nwe);

        System.Console.ReadKey(true);
    }
}

```
> 2 votes

---
Tags: code-golf, array
---