title: Draw me a shape

text:
# Question
Title: Draw me a shape
The game shapez.io has a *lot* of shapes. In my previous challenge, the object was to generate a random code for a shape. Now, your challenge is to render a shape.

# Specs

## Shapes

Each shape has a unique shortcode, for example:

is `CrWgRuSp` \- clockwise from top right, **r**ed **c**ircle, **g**reen **w**edge, **u**ncolored **r**ectangle, **p**urple **s**tar.

A *quadrant* is one of Rectangle (`R`), Circle (`C`), Star (`S`) or Wedge (`W`) painted with one of the below colours. The shortcode for these quadrants is the code for the shape concatenated to the code for the color, so a yellow star would be `Sy`. A quadrant can also be empty, with the code `--`.

Four quadrants concatenated together make a layer, the quadrants going clockwise from top-right. Layers will never be empty (`--------`).

Finally, between one and four layers stacked on top of each other (joined by `:`, lowest first) make a shape. For example, `CyCyCyCy:SrSrSrSr` looks like:

## Colours

The colours are as follows:

* uncolored / `u` / grey - #AAAAAA
* red / `r` \- #FC666A
* blue / `b` \- #66A7FF
* green / `g` \- #78FF65
* purple / `p` \- #DD66FF
* yellow / `y` \- #FDF52A
* cyan / `c` \- #87FFF5
* white / `w` \- #FFFFFF
* border - #555555

## Sizes

Given a constant \\$a\\$, the width of a single border, the shape sizes are as follows:

| Shape | Spec | Image |
| --- | --- | --- |
| Circle | A perfectly circular arc going out to 9a each way |  |
| Rectangle | A square with side 9a |  |
| Wedge | A shape with one side going out to 9a, the other going along the base to 5.75a before going diagonally to 9a. |  |
| Star | Both edges going out to 5.75a before going diagonally out to 9a and meeting up. |  |

These need to be multiplied by the scale factor for the correct layer:

* layer 1 (bottom) - 1
* layer 2 - \\$\frac{7}{9}\\$
* layer 3 - \\$\frac{19}{36}\\$
* layer 4 - \\$\frac{5}{18}\\$

You should render your shape with a value of \\$a ≥ 10\\$ pixels - your choice of the size.

Note: All sizes are approximations - If you have a better estimate, let me know.

All sizes are flexible within 1%.

You may take either a shape shortcode (layers joined by `:`), a list of layer shortcodes, or a list of lists of quadrant shortcodes.

# Scoring

This is , shortest wins!

# Testcases

`CyCyCyCy:SrSrSrSr` \-

`CuCuCuCu:------Cy` \-

`------Cg:------Cr` \-

`CrSyWgRb` \-

`Cr------:------Cr:Cr------:------Cr` \-

Note that you *don't* have to render the pale-grey circle in the background.

# Answer
> 9 votes
## JavaScript (ES10) + SVG (HTML5), ~~407~~ ~~387~~ ~~365~~ 340 bytes

```
g=s=>s.split`:`.map(s=>s.match(/../g)||[]);f=
l=>'<svg viewBox=-1350,-1350,2700,2700 stroke=#555>'+l.map((q,i)=>q.map(([s,c],o)=>`<path d=M0,0v-${{C:'36a36,36,0,0,1,36,',R:'36h36v',W:'23l36,-13v',S:'23l36,-13l-13,'}[s]}36z fill=#${"FDF52A/FC666A/66A7FF/87FFF5/AAA//FFF/78FF65/D6F".split`/`[parseInt(c,36)%17%9]} transform=rotate(${o*90})scale(${q=35-i*9+!i}) stroke-width=${108/q} />`))
```

```
<input oninput=o.innerHTML=f(g(this.value))><div id=o>
```

Takes input as a list of list and outputs SVG source parseable by HTML5. Note that as it's scalable I can't really specify what the value of `a` is, it's always just big enough to fit the width of the window. At the start is the `svg` element definition, followed by a `path` element for each of the (possibly 16) quadrants, sized, coloured and rotated appropriately. Edit: Saved 22 bytes thanks to @Arnauld (although 7 of those bytes should have been obvious, sigh...). Saved a further 18 bytes directly and 7 bytes indirectly thanks to @JohanduToit.

# Answer
> 4 votes
# LaTeX+Tikz, 770 bytes

This solution uses tikz's `scope` to implement the rotating and scaling.

```
\documentclass{standalone}\usepackage{xcolor,tikz}\usetikzlibrary{math}\begin{document}\def\h#1{\definecolor#1{HTML}}\h u{AAAAAA}\h r{FC666A}\h h{66A7FF}\h g{78FF65}\h p{DD66FF}\h y{FDF52A}\h c{87FFF5}\h w{FFFFFF}\def\R#1{\draw[fill=#1]rectangle(,);}\def\C#1{\draw[fill=#1](0,0)--(0,1)arc(90:0:1cm)--cycle;}\def\W#1{\draw[fill=#1](0,0)-|(,)--(0,0.639)--cycle;}\def\S#1{\draw[fill=#1](0,0)--(0,0.639)--(1,1)--(0.639,0)--cycle;}\expandafter\def\csname-\endcsname#1{\path(0,0)--(,);}\def\c#1#2{\csname#1\endcsname{#2}}\def~#1{\tikz[draw=black!66,line width=.11cm]{\def\a{#1}\foreach\l[count=\i from 0]in\a{\begin{scope}[scale=(37-9*\i+!\i)/36]\foreach\q[count=\j from 0]in\l\begin{scope}[rotate around={-90*\j:(0,0)}]{\expandafter\c\q}\end{scope};\end{scope}}}}\enddocument

```

## Result

This is the resulting pdf converted to svg with inkscape:

```
<!-- Created with Inkscape (http://www.inkscape.org/) --><svg   version="1.1"   id="svg2"   xml:space="preserve"   width="922.13867"   height="83.568001"   viewBox="0 0 922.13867 83.568001"   sodipodi:docname="document.svg"   inkscape:version="1.1 (c4e8f9ed74, 2021-05-24)"   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"   xmlns="http://www.w3.org/2000/svg"   xmlns:svg="http://www.w3.org/2000/svg"><defs     id="defs6" /><sodipodi:namedview     id="namedview4"     pagecolor="#ffffff"     bordercolor="#666666"     borderopacity="1.0"     inkscape:pageshadow="2"     inkscape:pageopacity="0.0"     inkscape:pagecheckerboard="0"     showgrid="false"     inkscape:zoom="5.5349593"     inkscape:cx="702.53453"     inkscape:cy="45.980465"     inkscape:window-width="1920"     inkscape:window-height="1042"     inkscape:window-x="0"     inkscape:window-y="18"     inkscape:window-maximized="1"     inkscape:current-layer="g8" /><g     id="g8"     inkscape:groupmode="layer"     inkscape:label="document"     transform="matrix(1.3333333,0,0,-1.3333333,0,83.568)"><g       id="g10"       transform="translate(83.002,29.921)"><g         id="g12"><g           id="g14"><g             id="g16"><g               id="g18"><g                 id="g20"><path                   d="M 0,0 V 29.92122 H 29.92122 V 0 Z"                   style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                   id="path22" /></g></g><g               id="g24" /><g               id="g26" /><g               id="g28" /></g></g></g><g         id="g30"         transform="translate(71.212)"><g           id="g32"><g             id="g34"><g               id="g36"><g                 id="g38"><g                   id="g40"><path                     d="M 0,0 V 29.92122 C 16.52524,29.92122 29.92122,16.52524 29.92122,0 Z"                     style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                     id="path42" /></g></g><g                 id="g44" /><g                 id="g46" /><g                 id="g48" /></g></g></g><g           id="g50"           transform="translate(71.211)"><g             id="g52"><g               id="g54"><g                 id="g56"><g                   id="g58"><g                     id="g60"><path                       d="M 0,0 H 29.92122 V 29.92122 L 0,19.11987 Z"                       style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                       id="path62" /></g></g><g                   id="g64" /><g                   id="g66" /><g                   id="g68" /></g></g></g><g             id="g70"             transform="translate(71.212)"><g               id="g72"><g                 id="g74"><g                   id="g76"><g                     id="g78"><g                       id="g80"><path                         d="M 0,0 V 19.11987 L 29.92122,29.92122 19.11987,0 Z"                         style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                         id="path82" /></g></g><g                     id="g84" /><g                     id="g86" /><g                     id="g88" /></g></g></g><g               id="g90"               transform="translate(72.629,1.417)"><g                 id="g92"><g                   id="g94"><g                     id="g96"><g                       id="g98"><g                         id="g100"><path                           d="M 0,0 V 29.92122 C 16.52524,29.92122 29.92122,16.52524 29.92122,0 Z"                           style="fill:#fdf52a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path102" /></g></g><g                       id="g104"><g                         id="g106"><path                           d="M 0,0 H 29.92122 C 29.92122,-16.52524 16.52524,-29.92122 0,-29.92122 Z"                           style="fill:#fdf52a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path108" /></g></g><g                       id="g110"><g                         id="g112"><path                           d="m 0,0 v -29.92122 c -16.52524,0 -29.92122,13.39598 -29.92122,29.92122 z"                           style="fill:#fdf52a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path114" /></g></g><g                       id="g116"><g                         id="g118"><path                           d="m 0,0 h -29.92122 c 0,16.52524 13.39598,29.92122 29.92122,29.92122 z"                           style="fill:#fdf52a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path120" /></g></g></g><g                     id="g122"><g                       id="g124"><g                         id="g126"><path                           d="M 0,0 V 14.08838 L 22.04732,22.04732 14.08838,0 Z"                           style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path128" /></g></g><g                       id="g130"><g                         id="g132"><path                           d="M 0,0 H 14.08838 L 22.04732,-22.04732 0,-14.08838 Z"                           style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path134" /></g></g><g                       id="g136"><g                         id="g138"><path                           d="M 0,0 V -14.08838 L -22.04732,-22.04732 -14.08838,0 Z"                           style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path140" /></g></g><g                       id="g142"><g                         id="g144"><path                           d="M 0,0 H -14.08838 L -22.04732,22.04732 0,14.08838 Z"                           style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                           id="path146" /></g></g></g></g></g><g                 id="g148"                 transform="translate(72.629)"><g                   id="g150"><g                     id="g152"><g                       id="g154"><g                         id="g156"><g                           id="g158"><path                             d="M 0,0 V 29.92122 C 16.52524,29.92122 29.92122,16.52524 29.92122,0 Z"                             style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                             id="path160" /></g></g><g                         id="g162"><g                           id="g164"><path                             d="M 0,0 H 29.92122 C 29.92122,-16.52524 16.52524,-29.92122 0,-29.92122 Z"                             style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                             id="path166" /></g></g><g                         id="g168"><g                           id="g170"><path                             d="m 0,0 v -29.92122 c -16.52524,0 -29.92122,13.39598 -29.92122,29.92122 z"                             style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                             id="path172" /></g></g><g                         id="g174"><g                           id="g176"><path                             d="m 0,0 h -29.92122 c 0,16.52524 13.39598,29.92122 29.92122,29.92122 z"                             style="fill:#a8a8a8;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                             id="path178" /></g></g></g><g                       id="g180"><g                         id="g182" /><g                         id="g184" /><g                         id="g186" /><g                         id="g188"><g                           id="g190"><path                             d="m 0,0 h -22.04732 c 0,12.17654 9.87078,22.04732 22.04732,22.04732 z"                             style="fill:#fdf52a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                             id="path192" /></g></g></g></g></g><g                   id="g194"                   transform="translate(72.63,-1.417)"><g                     id="g196"><g                       id="g198"><g                         id="g200"><g                           id="g202" /><g                           id="g204" /><g                           id="g206" /><g                           id="g208"><g                             id="g210"><path                               d="m 0,0 h -29.92122 c 0,16.52524 13.39598,29.92122 29.92122,29.92122 z"                               style="fill:#78ff65;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                               id="path212" /></g></g></g><g                         id="g214"><g                           id="g216" /><g                           id="g218" /><g                           id="g220" /><g                           id="g222"><g                             id="g224"><path                               d="m 0,0 h -22.04732 c 0,12.17654 9.87078,22.04732 22.04732,22.04732 z"                               style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                               id="path226" /></g></g></g></g></g><g                     id="g228"                     transform="translate(71.211,1.417)"><g                       id="g230"><g                         id="g232"><g                           id="g234"><g                             id="g236"><g                               id="g238"><path                                 d="M 0,0 V 29.92122 C 16.52524,29.92122 29.92122,16.52524 29.92122,0 Z"                                 style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                 id="path240" /></g></g><g                             id="g242"><g                               id="g244"><path                                 d="M 0,0 H 19.11987 L 29.92122,-29.92122 0,-19.11987 Z"                                 style="fill:#fdf52a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                 id="path246" /></g></g><g                             id="g248"><g                               id="g250"><path                                 d="M 0,0 H -29.92122 V -29.92122 L 0,-19.11987 Z"                                 style="fill:#78ff65;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                 id="path252" /></g></g><g                             id="g254"><g                               id="g256"><path                                 d="M 0,0 H -29.92122 V 29.92122 H 0 Z"                                 style="fill:#66a7ff;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                 id="path258" /></g></g></g></g></g><g                       id="g260"                       transform="translate(71.212,-1.417)"><g                         id="g262"><g                           id="g264"><g                             id="g266"><g                               id="g268"><g                                 id="g270"><path                                   d="M 0,0 V 29.92122 C 16.52524,29.92122 29.92122,16.52524 29.92122,0 Z"                                   style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                   id="path272" /></g></g><g                               id="g274" /><g                               id="g276" /><g                               id="g278" /></g><g                             id="g280"><g                               id="g282" /><g                               id="g284" /><g                               id="g286" /><g                               id="g288"><g                                 id="g290"><path                                   d="m 0,0 h -22.04732 c 0,12.17654 9.87078,22.04732 22.04732,22.04732 z"                                   style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                   id="path292" /></g></g></g><g                             id="g294"><g                               id="g296"><g                                 id="g298"><path                                   d="M 0,0 V 14.9606 C 8.26262,14.9606 14.9606,8.26262 14.9606,0 Z"                                   style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                   id="path300" /></g></g><g                               id="g302" /><g                               id="g304" /><g                               id="g306" /></g><g                             id="g308"><g                               id="g310" /><g                               id="g312" /><g                               id="g314" /><g                               id="g316"><g                                 id="g318"><path                                   d="m 0,0 h -7.8739 c 0,4.34868 3.52522,7.8739 7.8739,7.8739 z"                                   style="fill:#fc666a;fill-opacity:1;fill-rule:nonzero;stroke:#575757;stroke-width:2.83484;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:10;stroke-dasharray:none;stroke-opacity:1"                                   id="path320" /></g></g></g></g></g></g></g></g></g></g></g></g></g></g></g></svg>
```

## Formatted Code and Usage

<pre><code>\documentclass{standalone}
\usepackage{xcolor,tikz}
\usetikzlibrary{math}
\begin{document}
% define the color shorthands
\def\h#1{\definecolor#1{HTML}}
\h u{AAAAAA}
\h r{FC666A}
\h b{66A7FF}
\h g{78FF65}
\h p{DD66FF}
\h y{FDF52A}
\h c{87FFF5}
\h w{FFFFFF}
% define commands that draw a shape
\def\R#1{\draw[fill=#1]rectangle(,);}
\def\C#1{\draw[fill=#1](0,0)--(0,1)arc(90:0:1cm)--cycle;}
\def\W#1{\draw[fill=#1](0,0)-|(,)--(0,0.639)--cycle;}
\def\S#1{\draw[fill=#1](0,0)--(0,0.639)--(1,1)--(0.639,0)--cycle;}
\expandafter\def\csname-\endcsname#1{\path(0,0)--(,);}
% define the command that parses the shape and the colour and calls the shape command
\def\c#1#2{\csname#1\endcsname{#2}}
\def~#1{
    \tikz[draw=black!66,line width=.11cm]{
        \def\a{#1}
        \foreach \l [count=\i from 0] in \a{
            \begin{scope}[scale=(37-9*\i+!\i)/36]
                \foreach \q [count=\j from 0] in \l
                    \begin{scope}[rotate around={-90*\j:(0,0)}]{
                        \expandafter\c\q
                    }
                    \end{scope}
                ;
            \end{scope}
        }
    }
}
~{{Ru,--,--,--}}
~{{Cu,--,--,--}}
~{{Wu,--,--,--}}
~{{Su,--,--,--}}

~{{Cy,Cy,Cy,Cy},{Sr,Sr,Sr,Sr}}
~{{Cu,Cu,Cu,Cu},{--,--,--,Cy}}
~{{--,--,--,Cg},{--,--,--,Cr}}

~{{Cr,Sy,Wg,Rb}}
~{{Cr,--,--,--},{--,--,--,Cr},{Cr,--,--,--},{--,--,--,Cr}}
\enddocument
```
</code></pre>

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


title: Counting and so on

text:
# Question
Title: Counting and so on
## Content

You count numbers every day (I think), and most of you know how to count properly, the one next to `1` is `2`, and the next is `3`, so go on, no matter what number you receive, you can easily know what next number is.

Anyway, the program doesn't know, they are incredibly stupid, if I make a program shaped like `1`, it doesn't count to `2` for me. We need to solve that asap.

## Task

Write a program shaped `1` that produces a program shaped `2`, which chains and produces the next number, until the program failed and produces a number other than it should be.

## Shapes

your number should shaped like:

```
  #      ###   ###    # #  ###  ###  ###  ###  ###  ###
  #        #     #    # #  #    #      #  # #  # #  # #
  #      ###   ###    ###  ###  ###    #  ###  ###  # #
  #      #       #      #    #  # #    #  # #    #  # #
  #      ###   ###      #  ###  ###    #  ###    #  ###

```

It can be enlarged, twisted, be longer or shorter, as long as it Resembles the shape:

```
Acceptable:
 #####  ######  ### resembles 9
 ##  #  #    #  # #
 ##  #  ######  ###
 #####       #  ###
     #       #    #
     #       #    #
             #

Not acceptable:

  ###   #####   ###  ####
  ###   # #     # #  # ##
    #   ###     ###  ###
    #     #      #     #
          #      #     #
Those does NOT resembles 9

```

```
Acceptable reshape:

Original shape:

   ###               ####
   # #      widen    #  #
   ###     ------->  ####
     #                  #
     #                  #

           extend   ###       shorten   ###
           -------> # #   or            # #
                    ###                 ###
                      #                   #
                      #
                      #

          lengthen  ###
           -------> # #
                    # #
                    ###
                      #
                      #

     enlarge line   ###      ####      ####      ###           ###
           -------> ###  or  # ##  or  ## #  or  # #  but not  # # (this is
                    # #      ####      ####      ###           ###  not 9
                    ###        ##         #      ###           ###  but a 0)
                      #        ##         #        #           ###
                      #

```

You can do 1 or more of those actions on the same digit for any amount of units, for example:

```
   #####
   #  ##
   #  ##
   #####
      ##
      ##
      ##
      ##

```

Is Widened, extended, enlarged, and lengthened.

The original number should be obtained if you repeatedly removing one out of two consecutive identical rows or columns.

For digits that contain a hole in it (6, 8, 9, 0), the hole should exist (length, wide does not matter).

For U-shaped holes (2, 3, 4, 5, 6), those should have at least one empty byte that resembles a hole:

```
  ###  is done by shortening, and then enlarge line.
   ##
  ###  Acceptable.
   ##
  ###

```

For numbers that have more than one digit, digits should have at least one spacing between them, and they should not be connected in any way:

```
  #  ###
  #    #
  #  ###
  #  #
     ###

```

In case someone built a super large program, I am limiting first number's (1) byte count to be under 10k.

## Rules

* No standard loopholes
* Takes no input and outputs a program.
* You should output in the very same language you used on the previous number.

## Scoring

Your score is the highest number you chained until break.

For example, your code failed to generate 21, your score will be 20. In this case, the `20` program could be anything as long as it fits number rules, may also be non-program.

If there is infinity score exist, it counts as an infinity score.

for tie breaker, It would be the lowest total bytes count until the number 1000.

Whoever gets the largest number is the overall winner. (Grand prize)

And also individual winners for each language too. (individual prize)

# Answer
> 33 votes
# Python 3, infinity points

```
exec('exec("N=2%F=@@@%Q=chr'
'(39)*3%def?magic(s,N,W,H=N'
'one):%?if?H?is?None:%??H?='
'?W//2%?L=[%?@###,#,###,###'
',#?#,###,###,###,###,###@.'
'split(@,@),%?@#?#,#,??#,??'
'#,#?#,#??,#??,??#,#?#,#?#@'
'.split(@,@),%?@#?#,#,###,#'
'##,###,###,###,??#,###,###'
'@.split(@,@),%?@#?#,#,#??,'
'??#,??#,??#,#?#,??#,#?#,??'
'#@.split(@,@),%?@###,#,###'
',###,??#,###,###,??#,###,?'
'?#@.split(@,@)]%?Z=@@%?s=s'
'.replace(chr(32),chr(63)).'
'replace(chr(34),chr(33)).r'
'eplace(chr(39),chr(64)).re'
'place(chr(10),chr(37))%?s='
'f@exec({chr(39)}exec(!{s}!'
'.replace(chr(63),chr(32)).'
'replace(chr(33),chr(34)).r'
'eplace(chr(64),chr(39)).re'
'place(chr(37),chr(10))){ch'
'r(39)})@%?I=0%?done=False%'
'?for?i?in?range(5):%??for?'
'_?in?range(H):%???z=@?@.jo'
'in(L[i][int(j)]for?j?in?st'
'r(N))+@?@%???k=0%???for?j?'
'in?z:%????if?j==@#@:%?????'
'k+=1%????else:%?????if?k:%'
'??????k*=W%??????if?I==0:%'
'???????Z+=s[:k-1]+!@!%????'
'???I=k-1%??????else:%?????'
'??z=s[I:I+k-2]%???????if?l'
'en(z)?==?0:%????????Z+=@#@'
'*k%???????elif?len(z)?<?k-'
'2:%????????Z+=(!@!+z).ljus'
't(k,@#@)%????????I+=k%????'
'????done=True%???????else:'
'%????????if?z[-1]==!@!:%??'
'???????Z+=!@!+z+@)@%??????'
'???I+=k%?????????done=True'
'%????????elif?z[-2]==!@!:%'
'?????????Z+=!@!+z+@#@%????'
'?????I+=k%?????????done=Tr'
'ue%????????else:%?????????'
'Z+=!@!+z+!@!%?????????I+=k'
'-2%?????Z+=@?@*W%?????k=0%'
'???Z+=chr(10)%?if?done:?re'
'turn?Z[:-1]%def?f(s):%?fro'
'm?itertools?import?count%?'
'print(next(filter(None,(ma'
'gic(s,N,w)?for?w?in?count('
'7)))))%@@@%exec(F)%templat'
'e=@@@N={}%F={}{}{}%exec(F)'
'%template={}{}{}%S=templat'
'e.format(N+1,Q,F,Q,Q,templ'
'ate,Q)%f(S)@@@%S=template.'
'format(N+1,Q,F,Q,Q,templat'
'e,Q)%f(S)".replace(chr(63)'
',chr(32)).replace(chr(33),'
'chr(34)).replace(chr(64),c'
'hr(39)).replace(chr(37),ch'
'r(10)))')##################
############################
############################
############################
############################
############################
############################

```

Try it online!

Here's the code that generates the 1

The total length of the first 1000 programs (including 1) is 3961370 bytes

The main function of interest takes any string without `!`, `?`, `@`, or `%` and uses those to escape (space), `\n`, `'`, `"`. That makes it easy to split up the big exec string, since it has nothing annoying anymore.

Here's the number 1234567890 as generated by the program. (At the TIO link, you can see how it has to increase the size of 1234567891 because it couldn't fit)

```
exec(''       'exec("N=1234567891%'       'F=@@@%Q=chr(39)*3%d'       'ef?ma'       'gic(s'       ',N,W,H=None):%?if?H'       '?is?None:%??H?=?W//'       '2%?L=[%?@###,#,###,'       '###,#?#,###,###,###'       ',###,###@.split(@,@'       '),%?@#?#,#,??#,??#,'
'#?#,#'       '??,#??,??#,#?#,#?#@'       '.split(@,@),%?@#?#,'       '#,###'       ',###,'       '###,###,###,??#,###'       ',###@.split(@,@),%?'       '@#?#,#,#??,??#,??#,'       '??#,#?#,??#,#?#,??#'       '@.split(@,@),%?@###'       ',#,###,###,??#,###,'
'###,?'       '?#,###,??#@.split(@'       ',@)]%?Z=@@%?s=s.rep'       'lace('       'chr(3'       '2),chr(63)).replace'       '(chr(34),chr(33)).r'       'eplace(chr(39),chr('       '64)).replace(chr(10'       '),chr(37))%?s=f@exe'       'c({chr(39)}exec(!{s'
'}!.re'                     'place'                     '(chr('       '63),c'       'hr(32'       ')).re'                     'place'                                   '(chr('       '33),c'       'hr(34'       ')).re'       'place'       '(chr('       '64),c'
'hr(39'                     ')).re'                     'place'       '(chr('       '37),c'       'hr(10'                     '))){c'                                   'hr(39'       ')})@%'       '?I=0%'       '?done'       '=Fals'       'e%?fo'       'r?i?i'
'n?ran'                     'ge(5)'                     ':%??f'       'or?_?'       'in?ra'       'nge(H'                     '):%??'                                   '?z=@?'       '@.joi'       'n(L[i'       '][int'       '(j)]f'       'or?j?'       'in?st'
'r(N))'       '+@?@%???k=0%???for?'       'j?in?z:%????if?j==@'       '#@:%?????k+=1%????e'       'lse:%?????if?k:%???'       '???k*=W%??????if?I='                     '=0:%?'       '??????Z+=s[:k-1]+!@'       '!%???????I=k-1%????'       '??els'       'e:%??'
'?????'       'z=s[I:I+k-2]%??????'       '?if?len(z)?==?0:%??'       '??????Z+=@#@*k%????'       '???elif?len(z)?<?k-'       '2:%????????Z+=(!@!+'                     'z).lj'       'ust(k,@#@)%????????'       'I+=k%????????done=T'       'rue%?'       '?????'
'?else'       ':%????????if?z[-1]='       '=!@!:%?????????Z+=!'       '@!+z+@)@%?????????I'       '+=k%?????????done=T'       'rue%????????elif?z['                     '-2]=='       '!@!:%?????????Z+=!@'       '!+z+@#@%?????????I+'       '=k%??'       '?????'
'??don'       'e=Tru'                                   'e%???'                     '?????'                     'else:'       '%????'       '?????'                     'Z+=!@'       '!+z+!'       '@!%??'                     '?????'       '??I+='       'k-2%?'
'????Z'       '+=@?@'                                   '*W%??'                     '???k='                     '0%???'       'Z+=ch'       'r(10)'                     '%?if?'       'done:'       '?retu'                     'rn?Z['       ':-1]%'       'def?f'
'(s):%'       '?from'                                   '?iter'                     'tools'                     '?impo'       'rt?co'       'unt%?'                     'print'       '(next'       '(filt'                     'er(No'       'ne,(m'       'agic('
's,N,w'       ')?for?w?in?count(7)'       '))))%@@@%exec(F)%te'                     'mplat'       'e=@@@N={}%F={}{}{}%'       'exec(F)%template={}'                     '{}{}%'       'S=template.format(N'                     '+1,Q,'       'F,Q,Q,template,Q)%f'
'(S)@@'       '@%S=template.format'       '(N+1,Q,F,Q,Q,templa'                     'te,Q)'       '%f(S)".replace(chr('       '63),chr(32)).replac'                     'e(chr'       '(33),chr(34)).repla'                     'ce(ch'       'r(64),chr(39)).repl'
'ace(c'       'hr(37),chr(10)))')##       #####################                     #######       #####################       #####################                     #######       #####################                     #######       #####################

```

Try it online!

# Answer
> 8 votes
# Jelly, score infinity, ~~134~~ 111 bytes for 1, 597940 bytes for 1..1000

```
“ØJṫ-3ØėṖ¤,“DịI¢I¤ȷṢI£⁽⁽IȥbI£ḤYI¤<⁻ID-I¤<⁽I¡~øIŀḊEḃ65ḃ2EaOṛj0z0x€0¦F¥€;ṪA$ṾƊ;I©Vy¥vƭ/OUƊɼL¤Ua1¦®ṚUo⁶Y”;©2Vy¥vƭ/

```

Try it online!

A full program that takes no arguments and prints the next program. Should work for any integer - to try a different output, just change the number 2 after the `©` to something else. This uses something similar to the minimum possible shapes for each number as suggested by @Bubbler but I’ve added a zero. The left-hand most digit has its right-hand column widened to accommodate the program, which is then placed in the bottom row. All other non-spaces are replaced by the right link, .

## Example program for 9876543210

```
    ṛṛṛ     ṛṛṛ ṛṛṛ     ṛṛṛ ṛṛṛ
ṛṛṛ ṛ ṛ     ṛ   ṛ         ṛ   ṛ
ṛ ṛ ṛṛṛ     ṛṛṛ ṛṛṛ ṛ ṛ ṛṛṛ ṛṛṛ   ṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛ
ṛṛṛ ṛ ṛ ṛṛṛ ṛ ṛ   ṛ ṛṛṛ   ṛ ṛ     ṛ ṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛṛ
  ṛ ṛṛṛ  ṛṛ ṛṛṛ ṛṛṛ   ṛ ṛṛṛ ṛṛṛ ṛ ṛṛ“ØJṫ-3ØėṖ¤,”,“DịI¢I¤ȷṢI£⁽⁽IȥbI£ḤYI¤<⁻ID-I¤<⁽I¡~øIŀḊEḃ65ḃ2EaOṛj0z0x€0¦F¥€;ṪA$ṾƊ;I©Vy¥vƭ/OUƊɼL¤Ua1¦®ṚUo⁶Y”,9876543211©Vy¥vƭ/

```

Try it online!

## Explanation (outdated)

```
[“&<-”,[”“,”’,””]],“D…Y”,2      | Literal list of [["&<-","“’”"],"D…Y",2]
                          ©     | Copy this list to the register
                             ƭ/ | Reduce using:
                           y    | 1. translate (so the D…Y item has "&" replaced by "“", "<" by "’" and "-" by "”")
                            v   | 2. Eval (so the translated string is evaluated as a program using 2 as its argument

```

## Explanation of the program that’s built by the main program (also outdated)

This is split into parts to make it easier to read; these are all a single link, though. It takes an integer argument and also expects the original list of three items in the main program to be in the register.

```
   “œ…’       ¤     | Starting with [7814, 233918, 203174, 39260, 210860, 241612, 15754, 241614, 86334, 54574]
            Ɗ       | - Do the following as a monad:
       ḃ62          | - Convert to bijective base 62
          ḃ2        | - Convert to bijective base 2
             ’      | - Subtract 1
 Dị                 | Now, index into this list of binary digits using the digits of the link’s argument
               j0   | Join with zeroes
                 z0 | Transpose, filling with zeros

                 Ʋ | Starting with the link’s argument:
      +1           | - Add 1
        D          | - Convert to decimal digits
         L         | - Length
                Ʋ  | - Following as a monad:
          132+     | - Add 132
              1;   | - Prepend 1 (call this y)
    ¥€             | For each row of the output from the first part:
 x"                | - Repeat the number of times indicated by y, with arguments zipped
   F               | - Flatten

 ḷ              ɗɼ$ | Do the following to the register, but preserve the existing working value of the link (output from previous part):
       Ʋ            | - Following as a monad:
  Ṫ                 |   - Tail
   +1               |   - Add 1
     ;@             |   - Append to the end of the list
        Ṿ           | - Uneval
         Ż   Ɗ}¡    | - Prepend a zero if the following is true when applied to the output from the previous part:
          ¬         |   - Not
           Ḣ        |   - Head
            Ḣ       |   - Head

 aⱮ”¹                  | And with "¹"
     a1¦®;“©yvƭ/”¤     | And the first row with the register after appending "©yvƭ/" to it
                  Ṛ    | Reverse
                   o⁶  | Or with space
                     Y | Join with newlines

```

---
Tags: code-challenge, counting, code-generation
---


# Question
Title: Minimum number of numbers to sum to exactly n
First question here, don't yell at me if this is a duplicate or a bad challenge.

# Introduction

I thought of this challenge myself, and it seems to be a good basic puzzle for beginner code-golfers. It also might help me decide which code-golfing language to learn.

# Challenge

Given an array of integers that are less than or equal to `n`, output or return the minimum number of numbers from the array that sum up to exactly `n`.

You can choose to write a function or a full program.

### Input

You can safely assume `0 <= n < 2^31`.

Take an array or list of any kind (`vector` for C++ or Java's `LinkedList` are allowed), along with `n` and an optional parameter `length`, which specifies the length of the array.

You can also take the input as a space-separated string, separated from `n` by either a comma or a space:

```
1 5 7 3 7 3 6 3 2 6 3,10

1 5 7 3 7 3 6 3 2 6 3 10

```

if it is easier.

### Output

Output, or return the minimum number of numbers from the array that sum up to exactly `n`. Using the above example:

```
1 5 7 3 7 3 6 3 2 6 3,10

```

Your program should print:

```
2

```

because the minimum number of numbers that sum up to `10` is `2` (`7` and `3`).

In the case that there is no solution, print or return either a negative, `0`, "No solution" (though that would not be smart),  (as suggested), or any other falsy value, with the exception of an empty string.

# Example Input and Output

### Input:

```
1 5 7 3 7 3 6 3 2 6 3,10
143 1623 1646 16336 1624 983 122,18102
5 6 9,12

```

### Output:

```
2
3
-1

```

# Scoring

This is code-golf, so shortest code in bytes wins.

The top answer will be accepted on Christmas.

# Answer
## Pyth, ~~12~~ 11 bytes

```
lhafqsTQyEY

```

This takes `n` as the first line of input and the list on the second line.

```
lhafqsTQyEY     (Implicit: Q = 1st line of input; E = 2nd line)
         E      The list
        yE      Powerset (sorted by increasing length; empty set first)
   f            Filter by lambda T:
     sT         sum(T)
    q                  ==
       Q                  Q
   fqSTQyE      Sublists that sum to Q, sorted by increasing length
  a       Y     append an empty array (in case none match)
lh              take the length of the first element (0 for empty array)

```

Try it here.
> 7 votes

# Answer
# Japt, ~~30~~ ~~21~~ 18 bytes

Turns out there was a much more efficient method. ;)

```
Uà f_x ¥V} ml n- g

```

Test it online! (Note: `n-` has been changed to `n@X-Y}` for compatibility reasons)

This takes input as a space- or comma-separated array, followed by a number. Outputs `undefined` for test cases without solutions.

```
Uà f_  x ¥ V} ®   l} n- g
UàfmZ{Zx ==V} mZ{Zl} n- g

            // Implicit: U = input array, V = input integer
Uà fZ{   }  // Generate all possible combinations of U, then filter to only items Z where
Zx ==V      //   the sum of Z is equal to V.
mZ{Zl}      // Map each remaining combination to its length.
n-          // Sort by subtraction; smaller items end up in the front.
g           // Take the first item.
            // Implicit: output last expression

```

I can't believe I didn't think of this version when I originally wrote this...

Several optimizations have been made since then which come in handy here:

* A `U` at the beginning of the program can usually be left out.
* `Ã` is a shortcut for .
* `n` now sorts numbers properly by default.

Each of these takes off a byte, for a total of 15:

```
à f_x ¥VÃml n g

```

Test it online!
> 5 votes

# Answer
## Mathematica, ~~73~~ 65 bytes

```
Min[Length/@Select[IntegerPartitions[#2,#2,#],Sort@#==Union@#&]]&

```

Pure function, returns  if there is no solution.
> 1 votes

# Answer
# Python 3, 128 bytes

This isn't as golfed as I'd like it to be, but I'll work on it later.

```
from itertools import*
def s(a,n):
 for i in range(len(a)):
  for j in permutations(a,i+1):
   if sum(j)==n:return i+1
 return 0

```
> 1 votes

# Answer
# Mathematica, 45 bytes

```
Min@Cases[Subsets@#,i_/;Tr@i==12:>Length@#2]&

```
> 1 votes

# Answer
# CJam, 34 bytes

```
0q~_,2,m*\f.*{:+1$=},\;0f-{,}$0=,+

```

Try it online. The input format is the sum followed by the list of values, e.g.:

```
18102 [143 1623 1646 16336 1624 983 122]

```

Note that this will raise an exception if no solution is found. The exception goes to stderr when CJam is run from the command line, and the correct result (`0`) is still printed to stdout. So this meets the consensus established at Should submissions be allowed to exit with an error?

The code may look longer than you would expect. The main reason is that CJam has no built-in for generating combinations. Or at least that's my excuse, and I'm sticking to it.

Explanation:

```
0       Push 0 result for exception case.
q~      Get and interpret input.
_,      Copy and get length of input value list.
2,      Push [0 1].
m*      Cartesian power. This generates all possible lists of 0/1 values with the
        same length as the input value list.
\       Swap input value list to top.
f.*     Apply element-wise product of input value list with all 0/1 lists.
        We now have all combinations of values, with 0 in place of unused values.
{       Start filter block.
  :+      Sum values.
  1$      Copy target sum to top.
  =       Compare.
},      Filter.
\;      Swap target sum to top and discard.
0f-     Remove 0 values. We now have all solution lists.
{,}$    Sort by length.
0=      Get first solution, which after sorting is the shortest.
        This will raise an exception if the list of solutions is empty, bailing
        out with the initial 0 on the stack.
,       Get length of solution.
+       Add the 0 we initially pushed for the exception case.

```
> 1 votes

# Answer
# JavaScript (ES6), 84 bytes

```
f=(a,n,m=1e999,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0)&&m

```

## Explanation

Takes an `Array` of `Number`s and a `Number` as arguments. Returns a number of `Infinity` if no result. It is a recursive function that subtracts from `n` and removes each element from the array one-by-one until `n == 0`.

```
f=(a,n,m=1e999,x)=> // m and x are not passed, they are here to declare them in the local
                    //     scope instead of globally, initialise m to Infinity
  n&&               // if n == 0, return 0
  a.map((v,i)=>     // iterate over each number in a
    (x=[...a],      // x = copy of a
    x.splice(i,1),  // remove the added number from the array
    x=f(x,n-v)+1)   // x = result for the numbers in this array
      <m?m=x:0      // set m to minimum result
  )
  &&m               // return m

```

## Test

This test sets `m` to `Infinity` later instead of as a default argument to make it work in Chrome (instead of just Firefox).

```
var solution = f=(a,n,m,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0,m=1e999)&&m
```

```
Array (space-delimited) = <input type="text" id="array" value="143 1623 1646 16336 1624 983 122" /><br />
n = <input type="number" id="N" value="18102" /><br />
<button onclick="result.textContent=solution(array.value.split` `,N.value)">Go</button>
<pre id="result"></pre>
```
> 1 votes

# Answer
## Haskell, 72 bytes

```
import Data.List
n#l=head$sort[length x|x<-subsequences l,sum x==n]++[0]

```

Returns `0` if there's no solution.

Usage example: `10 # [1,5,7,3,7,3,6,3,2,6,3]` -\> `2`.

Find all sub-lists of the input list `l` which have a sum of `n`. Take the length of each such sub-list and sort. Append a `0` and take the first element.

If a singleton list is allowed for output, e.g. `[2]`, we can save 7 bytes: `n#l=minimum[length x|x<-subsequences l,sum x==n]`. In case of no solution, the empty list `[]` is returned.
> 1 votes

# Answer
# Vyxal, 9 bytes

```
ṗ'∑₀=;vLg

```

Try it Online!

```
ṗ         # Powerset
 '   ;    # Filtered by
  ∑₀=     # Sublists that sum to input
      vL  # Get length of each
        g # Minimum

```
> 1 votes

# Answer
# Jelly, 8 bytes

```
ŒPS=¥ƇẈṂ

```

Try it online!

Outputs `0` if there's no solution

## How it works

```
ŒPS=¥ƇẈṂ - Main link. Takes L on the left and n on the right
ŒP       - Powerset of L
    ¥Ƈ   - Keep those lists for which the following is true:
  S      -   The sum...
   =     -   ...equals n
      Ẉ  - Lengths of those kept
       Ṃ - Minimum

```
> 0 votes

# Answer
# Python 3.9, 101 bytes

```
def f(l,t):
 s={0:0}
 for i in l:s|={k+i:min(s[k]+1,s.get(k+i,s[k]+1))for k in s}
 return s.get(t,-1)

```

Try it online!

Note : the `|=` operators was introduced in python 3.9 but TIO doesn't support that version.

# Python 3, 105 bytes

```
def f(l,t):s={0:0};[s.update({k+i:min(s[k]+1,s.get(k+i,s[k]+1))for k in s})for i in l];return s.get(t,-1)

```

Try it online!

## Ungolfed version:

```
def f(l,t):
  s={0:0}              # initialize the reached numbers
  for i in l:          # iterate through the list
    new_s = {}           # create a dict for the newly reached numbers
    for k in s:          # iterate through all the reached numbers
      new_s[k+i] = min(s[k]+1,s.get(k+i,s[k]+1)) # set the new number to the minimal number of steps
    s.update(new_s)      # update out dict with the new values
  return s.get(t,-1)   # returns the number of steps or -1 if the number is unreachable

```

Try it online!

## Note:

there is probably some potential
> 0 votes

---
Tags: code-golf, number, combinatorics, integer-partitions
---


title: Jimmy these arrays down

text:
# Question
Title: Jimmy these arrays down
My coworker, Jimmy is kinda new to C/C++. He's also kind of a slow learner. Now, to be fair, his code always compiles, but he has some really sloppy habits. For example, everybody knows that you can define an array like this:

```
int spam[] = {4, 8, 15, 16, 23, 42};

```

Everybody that is, except for Jimmy. He is convinced that the *only* way to make an array is like this:

```
int spam[6];
spam[0] = 4;
spam[1] = 8;
spam[2] = 15;
spam[3] = 16;
spam[4] = 23;
spam[5] = 42;

```

I keep fixing this for him in code-review, but he won't learn. So I need you to write a tool that automagically does this for him when he commits¹.

# The challenge

I want you to write either a full program or a function that takes in a multiline string as input, and outputs the more compact version of the C array. The input will *always* follow this format, whitespace included:

```
identifier_one identifier_two[some_length];
identifier_two[0] = some_number;
identifier_two[1] = some_number;
identifier_two[2] = some_number;
...
identifier_two[some_length - 1] = some_number;

```

In short, the input will always be valid and well defined C. In more detail:

All of the identifiers will be made up of just letters and underscores. The length will always be at least one, and there will never be any missing or out of bounds indexes. You may also assume that the indexes are in order. For example:

```
foo bar[3];
bar[0] = 1
bar[2] = 9;

```

```
foo bar[1];
bar[0] = 1;
bar[1] = 3;

```

and

```
foo bar[3];
bar[2] = 9;
bar[0] = 1
bar[1] = 3

```

are all invalid inputs, and may cause undefined behavior in your submission. You may also assume that all of the numbers will be valid decimal numbers, negative or positive. The input will not have extraneous spaces. The output should always follow this format, whitespace included:

```
identifier_one identifier_two[] = {n1, n2, n3, ...};

```

Here is some sample data:

```
Input:
spam eggs[10];
eggs[0] = 0;
eggs[1] = 4;
eggs[2] = 8;
eggs[3] = -3;
eggs[4] = 3;
eggs[5] = 7;
eggs[6] = 888;
eggs[7] = 555;
eggs[8] = 0;
eggs[9] = -2;

Output:
spam eggs[] = {0, 4, 8, -3, 3, 7, 888, 555, 0, -2};

Input:
char ans[2];
ans[0] = 52;
ans[1] = 50;

Output:
char ans[] = {52, 50};

Input:
blah_blah quux[1];
quux[0] = 105;

Output:
blah_blah quux[] = {105};

```

You may take your input and output in any reasonable format, such as STDIN/STDOUT, function arguments and return value, reading and writing files etc. Standard loopholes apply. The shortest answer in bytes wins!

---

*¹This is passive-aggressive and a terrible idea. You did **not** get this idea from me.*

# Answer
> 8 votes
# Vim, ~~43~~ 36 bytes

You don't need to give Jimmy a script, just teach him to use a proper text editor. (literal returns for clarity)

```
:%s/.*=//|%s/;\n/,/<cr><cr>
3wcf ] = {<esc>
$s};

```

# Answer
> 7 votes
## CJam, ~~43~~ 36 bytes

```
qN/('[/~;"[] = {"@{S/W=W<}%", "*"};"

```

**Online Example**

**Explanation:**

```
qN/                                     |Read all lines to array
   ('[/~;                               |slice first line left of [
         "[] = {"                       |add formatting to stack
                 @                      |rotate to remaining lines
                  {      }%             |for each line in array
                   S/W=                 |split after last space
                       W<               |remove last character (;)
                           ", "*        |insert ", " to array
                                "};"    |add formatting

```

A big thanks to Martin Ender for the improvements on my first CJam answer.

# Answer
> 6 votes
# JavaScript (ES6), ~~65~~ ~~64~~ 63 bytes

```
s=>`${s.split`[`[0]}[] = {${s.match(/-?\d+(?=;)/g).join`, `}};`

```

# Answer
> 5 votes
## Retina, ~~30~~ 28 bytes

Byte count assumes ISO 8859-1 encoding.

```
\d+];¶.+
] = {
;¶.+=
,
;
};

```

Try it online!

### Explanation

We'll use the following input as an example:

```
spam eggs[4];
eggs[0] = 0;
eggs[1] = 4;
eggs[2] = 8;
eggs[3] = -3;

```

**Stage 1**

```
\d+];¶.+
] = {

```

Note that there's a trailing space on the first line.

We start by matching a number following by `];` and a linefeed, and then everything up to the last space on the next line. This match can only be found at the end of the first line (due to the `];`). All of this is replaced with `] = {`. That is, it transforms our example input to:

```
spam eggs[] = {0;
eggs[1] = 4;
eggs[2] = 8;
eggs[3] = -3;

```

**Stage 2**

```
;¶.+=
,

```

Now we match everything from a `;` up to the `=` on the next line and replace with a `,`. This transforms the string to:

```
spam eggs[] = {0, 4, 8, -3;

```

**Stage 3**

```
;
};

```

All that's left is fixing the end and we do this by replacing the only remaining `;` with `};`:

```
spam eggs[] = {0, 4, 8, -3};

```

# Answer
> 5 votes
## Julia, ~~112~~ ~~108~~ 105 Bytes

```
f(s)=string(split(s,'[')[1],"[] = {",join([m[1] for m in [eachmatch(r"= *(-?\d+)",s)...]],", "),"};")

```

**Explanation**

```
string(                                                         # build output string
split(s,'[')[1],                                                # get declaration (e.g. spam eggs)
"[] = {",                                                       # add [] = {
join(                                                           # collect numbers
    [m[1] for m in [eachmatch(r"= *(-?\d+)",s)...]],            # regex out (signed) numbers
    ", "),                                                      # and join comma separated
"};"                                                            # add };
)                                                               # close string(

```

Saved bytes by replacing collect(eachmatch()) with \[eachmatch()...\] and with a shorter regex

# Answer
> 4 votes
## Lua, 121 Bytes.

```
function g(s)print(s:gmatch('.-%[')()..'] = {'..s:gsub('.-\n','',1):gsub('.-([%d.-]+);\n?','%1, '):gsub(',%s+$','};'))end

```

## Explained

```
function g(s)
    print(                              -- Print, Self Explaintry.
        s:gmatch('.-%[')()..'] = {'     -- Find the 'header', match the first line's class and assignment name (everything up to the 'n]') and append that. Then, append ] = {.
                                        -- In the eggs example, this looks like; 'spam eggs[] = {' now
        ..                              -- concatenate...
        s:gsub('.-\n','',1)             -- the input, with the first line removed.
        :gsub('.-([%d.-]+);\n?','%1, ') -- Then that chunk is searched, quite boringly, a number followed by a semicolon, and the entire string is replaced with an array of those,
                                        -- EG, '1, 2, 3, 4, 5, 6, '
        :gsub(',%s+$','};')          -- Replace the final ', ' (if any) with a single '};', finishing our terrifying combination
    )
end

```

# Answer
> 3 votes
# C, 121 bytes

```
n=2;main(i){for(;putchar(getchar())^91;);for(printf("] = {");~scanf("%*[^=]%*c%d",&i);n=0)printf(", %d"+n,i);puts("};");}

```

# Answer
> 3 votes
## Batch, 160 bytes

```
@echo off
set/ps=
set s=%s:[=[] = {&rem %
set r=
:l
set t=
set/pt=
if "%t%"=="" echo %r%};&exit/b
set t=%t:* =%
set r=%r%%s%%t:~2,-1%
set s=,
goto l

```

Note: The line `set s=,` ends with a space. Takes input on STDIN. That weird line 3 takes the input (e.g. `int spam[6];` and changes the `[` into `[] = {&rem` resulting in `set s=int spam[] = {&rem 6];` which then gets interpreted as two statements, `set s=int spam[] = {` and `rem 6];`, the latter of which is a comment. Then for each line we delete the text up to the first space (because you can't use `=` in a pattern and the matching is non-greedy) and extract the value.

# Answer
> 3 votes
### Python 112 111

Very straightforward to me, please suggest any improvement that comes to mind.

```
def f(l):
 a,*b=l.split('\n')
 return a[:a.index('[')]+'[] = {'+', '.join(r.split(' = ')[1][:-1]for r in b)+'};'

# TEST

lines = """spam eggs[10];
eggs[0] = 0;
eggs[1] = 4;
eggs[2] = 8;
eggs[3] = -3;
eggs[4] = 3;
eggs[5] = 7;
eggs[6] = 888;
eggs[7] = 555;
eggs[8] = 0;
eggs[9] = -2;"""
print (f(lines))
assert f(lines) == 'spam eggs[] = {0, 4, 8, -3, 3, 7, 888, 555, 0, -2};'

```

# Answer
> 2 votes
# 05AB1E, ~~31~~ ~~30~~ 28 bytes

```
žh-|vy#¤¨ˆ\}¨… = ¯ïžuDÀÀ‡';J

```

**Explanation**

```
žh-¨                            # remove numbers and ";" from first input
    |v      }                   # for each of the rest of the inputs
      y#                        # split on spaces
        ¤¨                      # take the last element (number) minus the last char (";")
          ˆ\                    # store in global array and throw the rest of the list away
             … =                # push the string " = "
                 ¯ï             # push global array and convert to int
                   žuDÀÀ‡       # replace square brackets of array with curly ones
                         ';     # push ";"
                           J    # join everything and display

```

Try it online!

Saved a byte thanks to Adnan

# Answer
> 2 votes
## Perl, 42 + 2 (`-0p`) = 44 bytes

```
s%\d+].*%] = {@{[join",",/(-?\d+);/g]}};%s

```

Needs `-p` and `-0` flags to run. For instance :

```
perl -0pe 's%\d+].*%] = {@{[join",",/(-?\d+);/g]}};%s' <<< "blah_blah quux[1];
quux[0] = 105;"

```

# Answer
> 2 votes
# Java 7, ~~159~~ ~~158~~ ~~149~~ 154 bytes

```
String c(String[]a){a[0]=a[0].split("\\d")[0]+"] = {\b";for(String i:a)a[0]+=i.split("= [{]*")[1];return a[0].replace(";",", ").replaceFirst("..$","};");}

```

Multiple bytes saved thanks to *@cliffroot*.

**Ungolfed & test code:**

Try it here.

```
class M{
  static String c(String[] a){
    a[0] = a[0].split("\\d")[0] + "] = {\b";
    for(String i : a){
      a[0] += i.split("= [{]*")[1];
    }
    return a[0].replace(";", ", ").replaceFirst("..$", "};");
  }

  public static void main(String[] a){
    System.out.println(c(new String[]{ "spam eggs[10];", "eggs[0] = 0;", "eggs[1] = 4;",
      "eggs[2] = 8;", "eggs[3] = -3;", "eggs[4] = 3;", "eggs[5] = 7;", "eggs[6] = 888;",
      "eggs[7] = 555;", "eggs[8] = 0;", "eggs[9] = -2;" }));
    System.out.println(c(new String[]{ "char ans[2]", "ans[0] = 52;", "ans[1] = 50;" }));
    System.out.println(c(new String[]{ "blah_blah quux[1];", "quux[0] = 105;" }));
  }
}

```

**Output:**

```
spam eggs[] = {0, 4, 8, -3, 3, 7, 888, 555, 0, -2};
char ans[] = {52, 50};
blah_blah quux[] = {105};

```

# Answer
> 2 votes
# jq, 85 bytes

```
./"
"|(.[0]|gsub("\\d|;";""))+" = {"+(.[1:]|map([scan("-?\\d+")][-1])|join(", "))+"}"

```

Try it online!

I can probably remove the `map`, but not sure how to do it without breaking the thing. Otherwise quite satisfied with the solution.

# Answer
> 1 votes
# Jelly, 33 bytes

```
ỴḊḲ€Ṫ€K⁾;,yṖ“{“};”j
ỴḢḟØDṖ,⁾ =,ÇK

```

**TryItOnline**

How?

```
ỴḊḲ€Ṫ€K⁾;,yṖ“{“};”j - Link 1, parse and reform the values, same input as the Main link
Ỵ                   - split on line feeds
 Ḋ                  - dequeue (remove the first line)
  Ḳ€                - split each on spaces
    Ṫ€              - tail each (get the numbers with trailing ';')
      K             - join on spaces
       ⁾;,          - ";,"
          y         - map (replace ';' with ',')
           Ṗ        - pop (remove the last ',')
            “{“};”  - list of strings ["{","};"]
                  j - join (making "{" + "n0, n1, ,n2, ..." + "};")

ỴḢḟØDṖ,⁾ =,ÇK - Main link, takes one argument, the multiline string
Ỵ             - split on line feeds
 Ḣ            - head (just the first line)
   ØD         - digits yield "0123456789"
  ḟ           - filter out
     Ṗ        - pop (remove the trailing ';')
      ,   ,   - pair
       ⁾ =    - the string " ="
           Ç  - call the previous Link (1)
            K - join on spaces (add the space after the '=')

```

# Answer
> 1 votes
# Jelly, 27 bytes

```
Ỵ©ḢḟØDṖ“ = {”®Ḳ€Ṫ€Ṗ€j⁾, ⁾};

```

Try it online!

## Explanation

```
Ỵ         Split into lines
 ©Ḣ       Take the first one, store the others in ®
   ḟØD    Remove digits
      Ṗ   Remove trailing ;

“ = {”    Print a literal string

®         Recall the remaining lines
 Ḳ€       Split each into words
   Ṫ€     Keep each last word
     Ṗ€   Remove each trailing ;

j⁾,       Join by “, ”
    ⁾};   Literal “};”

```

# Answer
> 1 votes
# sed 51

```
1s,\[.*,[] = {,
:
N
s,\n.*= ,,
s/;/, /
$s/, $/};/
t

```

# Answer
> 1 votes
# Java, 106 bytes

String manipulation in Java is hell, as always.

```
a->a[0].join("",a).replaceAll(";\\w+\\[\\d+\\] = ",", ").replaceAll("\\d+\\], ","] = {").replace(";","};")

```

This is a pure regex answer. Make a single concatenated `String`, then perform `replaceXxx` until it's ok.

## Testing and ungolfed:

```
import java.util.function.Function;

public class Main {

  public static void main(String[] args) {
    Function<String[], String> f = a ->
        String.join("", a)                          // I think this would join. Not sure, though. Golfed into a[0].join because static members are accessible from instances.
            .replaceAll(";\\w+\\[\\d+\\] = ", ", ") // replace with regex
            .replaceAll("\\d+\\], ", "] = {")       // replace with regex
            .replace(";", "};");                    // replace no regex

    String[] spam = {
      "int spam[6];",
      "spam[0] = 4;",
      "spam[1] = 8;",
      "spam[2] = 15;",
      "spam[3] = 16;",
      "spam[4] = 23;",
      "spam[5] = 42;"
    };
    test(f, spam, "int spam[] = {4, 8, 15, 16, 23, 42};");

    String[] eggs = {
      "spam eggs[10];",
      "eggs[0] = 0;",
      "eggs[1] = 4;",
      "eggs[2] = 8;",
      "eggs[3] = -3;",
      "eggs[4] = 3;",
      "eggs[5] = 7;",
      "eggs[6] = 888;",
      "eggs[7] = 555;",
      "eggs[8] = 0;",
      "eggs[9] = -2;"
    };
    test(f, eggs, "spam eggs[] = {0, 4, 8, -3, 3, 7, 888, 555, 0, -2};");

    String[] ans = {
      "char ans[2];",
      "ans[0] = 52;",
      "ans[1] = 50;"
    };
    test(f, ans, "char ans[] = {52, 50};");

    String[] quux = {
      "blah_blah quux[1];",
      "quux[0] = 105;"
    };
    test(f, quux, "blah_blah quux[] = {105};");

  }

  static void test(Function<String[], String> f, String[] input, String expected) {
    System.out.printf("Result:   %s%nExpected: %s%n", f.apply(input), expected);
  }
}

```

# Answer
> 1 votes
# Pip `-r`, ~~32~~ 30 bytes

```
aRXI.']["] = {"(Z@>g@XI1)Jk'}]

```

Try it online!

### Explanation

The builtin regex for matching integers, `XI == `-?\d+``, came in really handy here.

```
aRXI.']["] = {"(Z@>g@XI1)Jk'}]
                                g is list of lines from stdin; a is first line (-r flag)
aR                              In the first line, replace
  XI.']                         integer followed by closing square bracket, with:
                 @>g             All but the first element in g
                    @XI          Find all (two) integers in each element
                Z                Zip that list of pairs into a pair of lists
               (       1)        and take the second list (the values)
                         Jk      Join on ", "
       [                     ]   Put the above string in a list
        "] = {"                  with this string before it
                           '}    and a curly brace after it
                                (The list is converted to a string when used as a
                                replacement; since there are no list-formatting flags
                                in use, its elements are simply concatenated together)

```

# Answer
> 1 votes
# Vyxal `aṪ`, 28 bytes

```
ḣƛ⌈t⌊;‛, j\{p\}+$kd$FṪ` = `„

```

Try it Online!

```
ḣ                            # Head extract
 ƛ   ;                       # Foreach line except the first
  ⌈t⌊                        # Split on spaces, get the last, parse an int
      ‛, j\{p\}+             # Join by commas and add {}
                $kd$FṪ       # Remove digits from line 1
                      ` = `„ # Push a ` = ` and prepare the stack for printing

```

# Answer
> 0 votes
## Ruby, 64 bytes

```
->{gets.split(?[)[0]+"[]={"+$<.map{|s|s.scan /\ -?\d+/}*?,+"};"}

```

# Answer
> 0 votes
# , ~~25~~, 24 bytes

```
3wC] = {òJd2f $s, òhC};

```

Try it online! This contains an unprintable `<esc>` character, so here is a hexdump:

```
0000000: 3377 435d 203d 207b 1bf2 4a64 3266 2024  3wC] = {..Jd2f $
0000010: 732c 20f2 6843 7d3b                      s, .hC};

```

Explanation:

```
3w                              "Move forward 3 words
  C     <esc>                   "Delete everything until the end of the line, and enter this text:
   ] = {                        "'] = {'
             ò         ò        "Recursively:
              J                 "  Join these two lines (which enters a space)
               d                "  Delete everything until you
                2f              "  (f)ind the (2)nd space
                   $            "  Move to the end of this line
                    s           "  Delete a character, and enter:
                     ,          "  ', '
                                "
                        h       "Move one character to the left
                         C      "Delete everything until the end of the line, and enter this text:
                          };    "'};'

```

# Answer
> 0 votes
# JavaScript, 125 bytes

I know it's longer than others, but I really wanted to use `eval`. Just for fun.

```
f=function(s){m=/^(\w+ )(\w+).*?(;.*)/.exec(s)
eval("var "+m[2]+"=new Array()"+m[3]+'alert(m[1]+m[2]+"={"+eval(m[2])+"};")')}

```

To run, paste the following into here:

```
s='int spam[6];\
spam[0] = 4;\
spam[1] = 8;\
spam[2] = 15;\
spam[3] = 16;\
spam[4] = 23;\
spam[5] = 42;'
f=function(s){m=/^(\w+ )(\w+).*?(;.*)/.exec(s)
eval("var "+m[2]+"=new Array()"+m[3]+'alert(m[1]+m[2]+"={"+eval(m[2])+"};")')}
f(s)

```

# Answer
> 0 votes
## Haxe, 234 bytes

```
function R(L:Array<String>){var S=L[0];var W=S.indexOf(" ");var T=S.substr(0,W),M=S.substring(W+1,S.indexOf("["));var r=[for(i in 1...L.length)L[i].substring(L[i].lastIndexOf(" ")+1,L[i].length-1)].join(', ');return'$T $M[] = {$r};';}

```

Long function names killed this :D

Try the testcases here!

# Answer
> 0 votes
# Julia 1.0, 81 bytes

```
!s=split(s,"[")[1]*"[] = {"*join([s[1] for s=eachmatch(r"(-*\d+);",s)],", ")*"};"

```

Try it online!

# Answer
> 0 votes
# Haskell, 80 bytes

```
f x=takeWhile(/='[')x++"[] = {"++drop 2([", "++w|w<-words x,w<"="]>>=init)++"};"

```

Try it online! Haskell is normally not very good at string-process-y challenges but it does OK here.

## Explanation

`takeWhile(/='[')x` extracts the typename and identifier `"spam eggs"`. Then we append `"[] = {" ++ drop 2 nums ++ "};"`, where `nums` is:

```
 [", "++w|w<-words x,w<"="]>>=init

```

The "words" (whitespace-delimited parts) of the input that are lexicographically less than `"="` happen to be all the digit-plus-semicolon parts like `"0;"`. This is because `'-'` \< `'0'..'9'` \< `'='` \< `'a'..'z'`.

The list comprehension says that to each such part, we prepend a comma and space:

```
[", 0;",", 4;",", 8;"]

```

Then `>>=init` (`concatMap init`) concatenates and chops off the semicolons:

```
", 0, 4, 8"

```

After which point `drop 2` gets rid of the initial comma.

# Answer
> 0 votes
# Pyth, 42 bytes 39 bytes

```
+:++:h.z"\d"k" = {"j", "mecd\ t.z\;k"}; // `ecd\ ` takes last word rather than regex replace

+:++:h.z"\d"k" = {"j", "m:d".* "kt.z\;k"};

```

Try it online!

## Explanation

```
+:++:h.z"\d"k" = {"j", "m:d".* "kt.z\;k"};
  ++                                         // Join the following strings:
    :h.z"\d"k                                //   input[0] with regex \d replaced for empty string
             " = {"                          //   Literal ` = {`
                   j", "                     //   Join with `, ` the following:
                        m:d".* "kt.z         //      Rest of input, removing everything before the numbers
                                             // Now our string looks like:
                                             //   spam eggs[]; = {0;, 4;, 8;, -3;, 3;, 7;, 888;, 555;, 0;, -2;
 :            [our string]          \;k      // Remove ';'
+                                      "};   // Append "};"

```

---
Tags: code-golf, string, parsing, c
---


title: The qvolume of an integer

text:
# Question
Title: The qvolume of an integer
It is ancient knowledge that every non-negative integer can be rewritten as the sum of four squared integers. For example the number 1 can be expressed as \\$0^2+0^2+0^2+1^2\\$. Or, in general, for any non-negative integer \\$n\\$, there exist integers \\$a,b,c,d\\$ such that

$$n = a^2+b^2+c^2+d^2$$

Joseph-Louis Lagrange proved this in the 1700s and so it is often called Lagrange's Theorem.

This is sometimes discussed in relation to quaternions – a type of number discovered by William Hamilton in the 1800s, represented as $$w+x\textbf{i}+y\textbf{j}+z\textbf{k}$$ where \\$w,x,y,z\\$ are real numbers, and \\$\textbf{i}, \textbf{j}\\$ and \\$\textbf{k}\\$ are distinct imaginary units that don't multiply commutatively. Specifically, it is discussed in relation to squaring each component of the quaternion $$w^2+x^2+y^2+z^2$$This quantity is sometimes called the norm, or squared norm, or also quadrance. Some modern proofs of Lagrange's Theorem use quaternions.

Rudolf Lipschitz studied quaternions with only integer components, called Lipschitz quaternions. Using quadrance, we can imagine that every Lipschitz quaternion can be thought of having a friend in the integers. For example quaternion \\$0+0\textbf{i}+0\textbf{j}+1\textbf{k}\\$ can be thought of as associated with the integer \\$1=0^2+0^2+0^2+1^2\\$. Also, if we go backwards, then every integer can be thought of as having a friend in the Lipschitz quaternions.

But there is an interesting detail of Lagrange's theorem – the summation is not unique. Each integer may have several different sets of four squares that can be summed to create it. For example, the number 1 can be expressed in 4 ways using non-negative integers (let us only consider non-negatives for this challenge): $$1=0^2+0^2+0^2+1^2$$ $$1=0^2+0^2+1^2+0^2$$ $$1=0^2+1^2+0^2+0^2$$ $$1=1^2+0^2+0^2+0^2$$

The summands are always squares of 0, or 1, but they can be in different positions in the expression.

For this challenge, let us also "sort" our summands lowest to highest, to eliminate duplicates, so that we could consider, for this exercise, that 1 only has one way of being represented as the sum of four squares:

$$1=0^2+0^2+0^2+1^2$$

Another example is the number 42, which can be expressed in four ways (again, only considering non-negative a,b,c,d, and eliminating duplicate component arrangements)

$$42=0^2+1^2+4^2+5^2$$ $$42=1^2+1^2+2^2+6^2$$ $$42=1^2+3^2+4^2+4^2$$ $$42=2^2+2^2+3^2+5^2$$

What if we imagine each of these different ways of expressing an integer as being associated to a specific quaternion? Then we could say the number 42 is associated with these four quaternions:

$$0+1\textbf{i}+4\textbf{j}+5\textbf{k}$$ $$1+1\textbf{i}+2\textbf{j}+6\textbf{k}$$ $$1+3\textbf{i}+4\textbf{j}+4\textbf{k}$$ $$2+2\textbf{i}+3\textbf{j}+5\textbf{k}$$

If we imagine the standard computer graphics interpretation of a quaternion, where \\$\textbf{i}\\$, \\$\textbf{j}\\$ and \\$\textbf{k}\\$ are vectors in three dimensional Euclidean space, and so the \\$x\\$, \\$y\\$ and \\$z\\$ components of the quaternion are 3 dimensional Cartesian coordinates, then we can imagine that each integer, through this thought process, can be associated with a set of 3 dimensional coordinates in space. For example, the number 42 is associated with the following four \\$(x,y,z)\\$ coordinates: $$(1,4,5),(1,2,6),(3,4,4),(2,3,5)$$

This can be thought of as a point cloud, or a set of points in space. Now, one interesting thing about a set of finite points in space is that you can always draw a minimal bounding box around them – a box that is big enough to fit all the points, but no bigger. If you imagine the box as being an ordinary box aligned with the \\$x,y,z\\$ axes, it is called an axis-aligned bounding box. The bounding box also has a volume, calculable by determining its width, length, and height, and multiplying them together.

We can then imagine the volume of a bounding box for the points formed by our quaternions. For the integer 1, we have, using the criteria of this exercise, one quaternion whose quadrance is 1, \\$0+0\textbf{i}+0\textbf{j}+1\textbf{k}\\$. This is a very simple point cloud, it only has one point, so it's bounding box has volume 0. For the integer 42, however, we have four quaternions, and so four points, around which we can draw a bounding box. The minimum point of the box is \\$(1,2,4)\\$ and the maximum is \\$(3,4,6)\\$ resulting in a width, length, and height of 2, 2, and 2, giving a volume of 8.

Let's say that for an integer \\$n\\$, the qvolume is the volume of the axis-aligned bounding box of all the 3D points formed by quaternions that have a quadrance equal to \\$n\\$, where the components of the quaternion \\$w+x\textbf{i}+y\textbf{j}+z\textbf{k}\\$ are non-negative and \\$w\<=x\<=y\<=z\\$.

Create a program or function that, given a single non-negative integer \\$n\\$, will output \\$n\\$'s qvolume.

Examples:

```
input -> output
0 -> 0
1 -> 0
31 -> 4
32 -> 0
42 -> 8
137 -> 96
1729 -> 10032

```

This is code-golf, smallest number of bytes wins.

# Answer
> 13 votes
# Wolfram Language (Mathematica), ~~67~~ 58 bytes

```
Volume@BoundingRegion[Rest/@PowersRepresentations[#,4,2]]&

```

Try it online!

```
                         ...&   Pure function:
PowersRepresentations[#,4,2]    Get the sorted reprs. of # as sums of 4 2nd powers
Rest/@                         Drop the first coordinate of each
BoundingRegion[...]            Find the bounding region, a Cuboid[] or Point[].
                               By default Mathematica finds an axis-aligned cuboid.
Volume                         Find volume; volume of a Point[] is 0.

```

# Answer
> 8 votes
# Jelly, 17 bytes

```
Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P

```

**Try it online!** (pretty slow - make it fast enough for all the test cases with a leading `½`)

### How?

```
Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P - Link: non-negative integer, n    e.g. 27
Ż                 - zero-range                            [0,1,2,...,27]
   4              - literal four                          4
 œċ               - combinations with replacement         [[0,0,0,0],[0,0,0,1],...,[0,0,0,27],[0,0,1,1],[0,0,1,2],...,[27,27,27,27]]
        Ƈ         - filter keep those for which:          e.g.: [0,1,1,5]
       ɗ          -   last three links as a dyad:
    ²             -     square (vectorises)                     [0,1,1,25]
     S            -     sum                                     27
      ⁼  ⁸        -     equal to? chain's left argument, n      1
                  -                                       -> [[0,1,1,5],[0,3,3,3],[1,1,3,4]]
          Z       - transpose                             [[0,0,1],[1,3,1],[1,3,3],[5,3,4]]
           Ḋ      - dequeue                               [[1,3,1],[1,3,3],[5,3,4]]
            Ṣ€    - sort each                             [[1,1,3],[1,3,3],[3,4,5]]
              I   - incremental differences (vectorises)  [[ 0,2 ],[ 2,0 ],[ 1,1 ]]
               §  - sum each                              [2,2,2]
                P - product                               8

```

# Answer
> 6 votes
# Haskell, ~~132~~ 123 bytes

```
z=zipWith
(!)=foldr1.z
h n=[0..n]
f n|p<-[[c,b,a]|a<-h n,b<-h a,c<-h b,d<-h c,a^2+b^2+c^2+d^2==n]=product$z(-)(max!p)$min!p

```

Try it online!

Pretty straightforward solution. Brute force all the possible solutions by iterating over all the values from 0 to n (way overkill but shorter bytecount). I output the point as a list so we can use @Lynn's magic `(!)` operator. That operator collapses each dimension with the function on the left side so `max!p` returns a list of size 3 which consists of the maximums along each dimension and `min!p` does the same for minimum. Then we just find the minimum size in each dimension (by subtracting the min value from the max with `z(-)`) and multiply them together.

Thanks a lot to @Lynn for taking off 9 bytes with some folding zip magic!

# Answer
> 5 votes
# Sledgehammer 0.2, 12 bytes

```
⡌⢎⣟⡊⢘⣚⡏⡨⠍⠁⡇⠨

```

Use with Mathematica 11.2 and this version of Sledgehammer, which predates the challenge. See edit history for a version that works in version 0.3, which has a GUI and generates a Mathematica expression.

This pushes the input to the stack and calls the sequence of commands

```
{intLiteral[4], intLiteral[2], call["PowersRepresentations", 3], call["Thread", 1], call["Rest", 1], call["Thread", 1], call["BoundingRegion", 1], call["Volume", 1]}

```

which is equivalent to evaluating the following Wolfram code derived from my Wolfram Language answer:

```
Volume[BoundingRegion[Thread@Rest@Thread@PowersRepresentations[#, 4, 2]]]&

```

Try it online!

# Answer
> 4 votes
# Python 2, 138 bytes

```
q=lambda n,x=0,*t:[t]*(n==0)if t[3:]else q(n-x*x,x,x,*t)+q(n,x+1,*t+(0,)*(x>n))
p=1
for l in zip(*q(input()))[:3]:p*=max(l)-min(l)
print p

```

Try it online!

Recursively generates the reverse-sorted quaternions with the given norm, then takes the product between the max and min of all possible values in the first three indices.

`itertools` might have had a shot if it didn't use ridiculously long names like `itertools.combinations_with_replacement`

**Python 2, 161 bytes**

```
from itertools import*
n=input();p=1
for l in zip(*[t[1:]for t in combinations_with_replacement(range(n+1),4)if sum(x*x for x in t)==n]):p*=max(l)-min(l)
print p

```

Try it online!

This is why `itertools` is never the answer.

# Answer
> 3 votes
# JavaScript (ES6),  ~~148~~  143 bytes

```
n=>(r=[[],[],[]]).map(a=>p*=a.length+~a.indexOf(1),(g=(s,k=0,a=[])=>a[3]?s||r.map(r=>r[a.pop()]=p=1):g(s-k*k,k,[...a,++k],k>s||g(s,k,a)))(n))|p

```

Try it online!

## Commented

We initialize an array \\$r\\$ with 3 empty arrays.

```
r = [ [], [], [] ]

```

For each valid value of \\$x\\$, we will set to \\$1\\$ the value at \\$x+1\\$ in the first array. Ditto for \\$y\\$ and \\$z\\$ with the 2nd and 3rd arrays respectively.

The dimensions of the bounding box will be deduced from the distance between the first and the last entry set to \\$1\\$ in these arrays.

### Step 1

To fill \\$r\\$, we use the recursive function \\$g\\$.

```
g = (              // g is a recursive function taking:
  s,               // s   = current sum, initially set to the input n
  k = 0,           // k   = next value to be squared
  a = []           // a[] = list of selected values
) =>               //
  a[3] ?           // if we have 4 values in a[]:
    s ||           //   if s is equal to zero (we've found a valid sum of 4 squares):
      r.map(r =>   //     for each array r[] in r[]:
        r[a.pop()] //       pop the last value from a[]
        = p = 1    //       and set the corresponding value in r[] to 1
                   //       (also initialize p to 1 for later use in step 2)
      )            //     end of map()
  :                // else:
    g(             //   do a recursive call:
      s - k * k,   //     subtract k² from s
      k,           //     pass k unchanged
      [...a, ++k], //     increment k and append it to a[]
      k > s ||     //     if k is less than or equal to s:
        g(s, k, a) //       do another recursive call with s and a[] unchanged
    )              //   end of outer recursive call

```

### Step 2

We can now compute the product \\$p\\$ of the dimensions.

```
r.map(a =>         // for each array a[] in r[]:
  p *=             //   multiply p by:
    a.length +     //     the length of a[]
    ~a.indexOf(1)  //     minus 1, minus the index of the first 1 in a[]
) | p              // end of map(); return p

```

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), 229 bytes

```
a=>{uint b=0,c=~0U,d,e,f=0,g=0,h=0,i=c,j=c,k=c;for(;b*b<=a;b++)for(c=b;c*c<=a;c++)for(d=c;d*d<=a;d++)for(e=d;e*e<=a;e++)if(b*b+c*c+d*d+e*e==a){f=c>f?c:f;g=d>g?d:g;h=e>h?e:h;i=c<i?c:i;j=d<j?d:j;k=e<k?e:k;}return(f-i)*(g-j)*(h-k);}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 18 bytes

```
Ý4ãʒnOQ}€{ζ¦ε{¥O}P

```

Try it online!

Port of Jonathan Allan's Jelly answer.

# Answer
> 2 votes
# Haskell, 104 bytes

```
n%i=(-).maximum<*>minimum$[t!!i|t<-mapM(:[0..n])[0..3],sum(map(^2)t)==n,scanr1 max t==t]
f n=n%0*n%1*n%2

```

Try it online!

*Thanks to Delfad0r for -1 byte and Lynn for 3 bytes*

To multiply the three dimensions, it turns out shortest to just write the product `f n=n%0*n%1*n%2` than to use any sort of loop. Here, `n%i` is the difference between the min and max of the `i`'th coordinate values, which are extracted with indexing `!!i`.

To generate the valid four-tuples, we take lists of four numbers from `[0..n]` whose squares sum to `n` and are in decreasing order. We check the reverse-sortedness of `t` with `scanr1 max t==t`, which sees if the running maximum of the reverse is itself, as Haskell doesn't have a built-in sort without a costly import. I tried various ways to recursively generate the four-tuples like in my Python answers, but they were all longer than this brute-force generate-and-filter way.

# Answer
> 1 votes
# jq, 164 bytes

```
. as$i|[range(.)]|[combinations(4)|select(map(.*.)|add==$i)|sort]|unique|[transpose[1:][]|sort|[.[:-1],.[1:]]|transpose|map(.[1]-.[0])|add//0]|reduce.[]as$j(1;.*$j)

```

Try it online!

The pairwise reduction can probably be better. For lower numbers, null is substituted with `0` for consistent output.

Idea from Jonathan Allan's answer.

-1 from ovs.

---
Tags: code-golf, complex-numbers
---


title: Distinct Sieves

text:
# Question
Title: Distinct Sieves
Given a list of integers, create a boolean mask such that the true indices can be used to filter the distinct values from the list. Which index is selected as the true one does not matter as long as only one of them is selected for each set of indices corresponding to identical values.

The input will be a non-empty list of non-negative integers in a format suitable for your language and the output will be a list of boolean values following the specification above. You are allowed to use your own definitions of truthy and falsy values in the output list.

In my examples below, I define `1` to be truthy and `0` to be falsy.

```
[5, 4, 7, 1]  Input
[1, 1, 1, 1]  Output
              Select only the values with with true indicies in the sieve
[5  4  7  1]  Contains zero duplicate values

[5, 9, 7, 5, 6, 0, 5]
[0, 1, 1, 1, 1, 1, 0]
[   9, 7, 5, 6, 0   ]

```

## Test Cases

When there is an `or`, it means that there are multiple valid outputs. If there is a trailing ellipsis `...` after the `or`, it means that not all of the possible outputs were listed.

```
[0] = [1]

[55] = [1]

[32, 44] = [1, 1]

[0, 0] = [1, 0] or [0, 1]

[9001, 9001, 9001] = [1, 0 , 0] or [0, 1, 0] or [0, 0, 1]

[5, 4, 7, 1] = [1, 1, 1, 1]

[1, 2, 3, 4, 3, 5] = [1, 1, 1, 1, 0, 1] or
                     [1, 1, 0, 1, 1, 1]

[5, 9, 7, 5, 6, 0, 5] = [1, 1, 1, 0, 1, 1, 0] or
                        [0, 1, 1, 1, 1, 1, 0] or
                        [0, 1, 1, 0, 1, 1, 1]

[0, 8, 6, 6, 3, 8, 7, 2] = [1, 1, 1, 0, 1, 0, 1, 1] or
                           [1, 0, 0, 1, 1, 1, 1, 1] or
                           [1, 0, 1, 0, 1, 1, 1, 1] or
                           [1, 1, 0, 1, 1, 0, 1, 1]

[45, 47, 47, 45, 24, 24, 24, 8, 47, 41, 47, 88]
= [1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1] or ...

[154, 993, 420, 154, 154, 689, 172, 417, 790, 175, 790, 790, 154, 172, 175, 175, 420, 417, 154, 175, 172, 175, 172, 993, 689, 993, 993, 790]
= [1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] or ...

```

## Rules

* This is so the shortest solution wins.
* Builtins are allowed!
* You are allowed to use your own definitions of truthy and falsy values in the output list. If you choose to do so, please state your definitions.
* The input will be a non-empty list of non-negative integers.
* You are free to choose between outputting only one of the sieves or multiple or even all of them. As long as each sieve is valid, it will be accepted.

# Answer
# MATL, ~~7~~ ~~6~~ 4 bytes

*1 byte saved thanks to @Luis*
*2 bytes saved thanks to @Dennis*

```
&=Rs

```

We define `1` to be truthy and all other values as falsey

**Try it Online**

All test cases

**Explanation**

```
    % Implicitly grab input array
&=  % 2D array of equality comparisons
R   % Get the upper triangular portion
s   % Sum down the columns
    % Implicitly display the result

```
> 11 votes

# Answer
# Jelly, 4 bytes

```
ĠṪ€Ṭ

```

Favors last occurrences. Try it online! or verify all test cases.

### How it works

```
ĠṪ€Ṭ  Main link. Argument: A (array)

Ġ     Group; paritition the indices of A according to their corresponding values.
 Ṫ€   Tail each; select the last index of each group.
   Ṭ  Untruth; generate a Boolean array with 1's at the specified indices.

```
> 9 votes

# Answer
## Python 3, ~~47~~ ~~35~~ ~~39~~ 36 bytes

```
lambda n:[n.pop(0)in n for x in n*1]

```

Pops the first item from the list, checks if it exists elsewhere in the list, and inserts `True` or `False` into a new list.

For this function, `False` indicates a distinct value, and `True` is otherwise (`True=0` and `False=1`)

*Thanks to Dennis for a ton of bytes*

Original, 47 bytes:

```
lambda n:[(1,0)[n.pop()in n]for x in[1]*len(n)]

```

Try it
> 8 votes

# Answer
# Pyth, 6 bytes

```
.eqxQb

```

Outputs a list of bools (`True` and `False`). Checks for each element in the input, if its index is equal to the index of the first occurence of the value. In other words, this is checking if each element is the first occurence.

In pythonic pseudocode:

```
.e      enumerated_map(lambda b,k:    # maps with b as value and k as index
  q       equal(
   xQb      Q.index(b),
            k),                       # implicit lambda variable
          Q)                          # implicit argument to map

```

Test it here.
> 7 votes

# Answer
# , 2 bytes

```
~:

```

This was where the idea for this challenge originated from. The builtin `~:` is called `Nub-Sieve` in J and creates a boolean list that performs the operation described in the challenge. Here, `1` represents `true` and `0` represents `false`.
> 6 votes

# Answer
# 05AB1E, 8 bytes

Code:

```
v¹ykN>Qˆ

```

Explanation:

```
y         # For each in the array
 ¹yk      # Get the index of that element in the array
    N>Q   # And see if it's equal to the index
       ˆ  # Add to the global array and implicitly output

```

Uses the **CP-1252** encoding. Try it online!.
> 6 votes

# Answer
## C#, 63 bytes

```
int[]l(List<int> i)=>i.Select((m,n)=>i.IndexOf(m)-n).ToArray();

```

I could also make it return 1 or 0 and therby make the parameter and return type the same one therby allowing me to make this a lambda expression by itself?

*some guidance would be appreciated*

**same type code**

```
    public static List<int>l(List<int>i){
        return i.Select((m,n)=>i.IndexOf(m)==n?1:0).ToList();
    }

```
> 4 votes

# Answer
# APL, 6 bytes

```
⍳∘⍴∊⍳⍨

```

Try it

Explanation:

```
   ⍳⍨  For each character in the string, get the index of its first occurrence
⍳∘⍴     Make a list 1 .. length of input
  ∊    Check if each index is present

```
> 4 votes

# Answer
## Python, 35 bytes

```
f=lambda l:l and[l.pop(0)in l]+f(l)

```

Uses `True` as the falsy value and `False` for the truthy value. Marks the last appearance of each element.

Selects the first element only if it doesn't appear among the remaining elements, then recurses to the rest of the list as long as it's non-empty. The `l.pop(0)` extracts the first element while also removing it.
> 3 votes

# Answer
## Retina, 23 bytes

```
(\d+)((?!.* \1\b))?
$#2

```

Input is a space-separated list. (Actually, other formats like `[1, 2, 3]` will also work as long as there's a space in front of each number except the first.)

Try it online! (Works on multiple linefeed-separated test cases at once.)

We simply turn each element into `0` if there's another copy of it later on in the input and into `1` otherwise.
> 3 votes

# Answer
## PowerShell v2+, 40 bytes

```
$a=@();$args[0]|%{(1,0)[$_-in$a];$a+=$_}

```

Creates an empty array `$a`. Then we take the input list via `$args[0]` and pipe that into a loop `|%{...}`. Each iteration we select either `1` or `0` from a pseudo-ternary based on whether the current element is in `$a` or not. Those selections are left on the pipeline. We then add the current element into the array `$a`. The pipeline elements are gathered up, and output as an array is implicit.

### Example:

*(output here with a newline separator, since that's the default `.ToString()` for an array)*

```
PS C:\Tools\Scripts\golfing> .\distinct-sieves.ps1 1,2,3,4,1,3,5,7
1
1
1
1
0
0
1
1

```
> 2 votes

# Answer
## JavaScript (ES6), 31 bytes

```
f=a=>a.map((e,i)=>i-a.indexOf(e))

```

Zero is truthy and other numbers are falsy.
> 1 votes

# Answer
## Mathematica, ~~53~~ 31 bytes

*Thanks to miles for giving me an idea that saved 22 bytes.*

```
s[[;;x++]]~FreeQ~#&/@(x=0;s=#)&

```
> 1 votes

# Answer
## Perl 5

```
push@o,map{$b=pop@a;(grep{/^$b$/}@a)?1:0}(1..~~@a);

```
> 1 votes

# Answer
# Java, 96 bytes

```
void s(int[]a){for(int i=0,j,n=a.length,b=1;i<n;a[i++]=b,b=1)for(j=i+1;j<n;)b=a[i]==a[j++]?0:b;}

```

Modifies the array in-place. Favours the last occurrence.

The truthy value is `1` while the falsey value is `0`.

Verify all testcases.

Ungolfed:

```
void sieve(int[]a){
    int n = a.length;
    for(int i=0;i<n;i++){
        int b = 1;
        for(int j=i+1;j<n;j++){
            if(a[i] == a[j]){
                b = 0;
            }
        }
        a[i] = b;
    }
}

```
> 1 votes

# Answer
## Actually, 11 bytes

```
;╗ñ`i@╜í=`M

```

Try it online!

Explanation:

```
;╗ñ`i@╜í=`M
;╗           save a copy of input in reg0
  ñ          enumerate
   `i@╜í=`M  for each (index, value) pair:
    i@         flatten, swap
      ╜í       first index in input of value
        =      compare equality

```
> 1 votes

# Answer
## Pyke, 4 bytes

```
F@oq

```

Try it here!

```
     - o = 0 #(Implicit)
F    - for i in input:
 @   -   input.index(i)
   q -  ^==V
  o  -   o+=1

```
> 1 votes

# Answer
## Haskell, ~~29~~ 27 bytes

```
f a=[elem x t|x:t<-tails a]

```

Uses `False` as true, `True` as false value:

```
λ> let f a=[elem x t|x:t<-tails a] in f [5, 9, 7, 5, 6, 0, 5]
[True,False,False,True,False,False,False]

```

You might have to `import Data.List` to use `tails` but, tryhaskell.org runs the code as is.
> 1 votes

# Answer
# PHP, ~~66~~ ~~62~~ 39 bytes

* accepts all atomic values (boolean, integer, float, string)
except for values evaluating to false (false, 0, "") and numeric strings ("1" equals 1)
* flags first occurence

**new version** (program, 37+2 bytes)
beats Java and (now again) C#. Even almost beats Python now. Happy.

```
<?foreach($a as$v)$u[$v]=print$u[$v]|0;

```
* +6 for PHP\>=5.4, +16-3 for a function
* prints undelimited list of `0` (true) and `1` (false)
insert `!` after `print` to invert
* usage: set `register_globals=On`, `short_open_tags=On` and `error_reporting=0` in `php.ini` for `php-cgi`
then call `php-cgi -f <filename> a[]=<value1> a[]=<value2> ...;echo""`;
* for PHP\>=5.4: replace `$a` with `$_GET[a]` (+6), set `short_open_tags=On` and `error_reporting=0`
* or replace `$a` with `array_slice($argv,1)` (+19), remove `<?`  (-2)
and call `php -d error_reporting=0 -r '<code>' <value1> <value2> ...;echo""`

**old version** (function, 62 bytes)

```
function f($a){foreach($a as$v)$u[$v]=1|$m[]=$u[$v];return$m;}

```
* returns array of `false` for true and `true` for false; (ouput as empty string or `1`)
insert `!` after `$m[]=` to invert
* There is another way for a qualified function with 55 bytes, too.

**tests** (on old version)

```
function out($a){if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',(strcmp(out($y),out($e))?'N':'Y'),"</td></tr>";$h='';}
$samples=[
    [0],[1],    [55],[1],    [32,44],[1,1],    [9001,9001,9001],[1,false,false],
    [5,4,7,1],[1,1,1,1],    [1,2,3,4,3,5],[1,1,1,1,false,1],
    [5,9,7,5,6,0,5],[1,1,1,false,1,1,false],    [0,8,6,6,3,8,7,2],[1,1,1,false,1,false,1,1],
    [45,47,47,45,24,24,24,8,47,41,47,88],[1,1,'','',1,'','',1,'',1,'',1],
    [154,993,420,154,154,689,172,417,790,175,790,790,154,172,175,
        175,420,417,154,175,172,175,172,993,689, 993,993,790],
        array_merge([1,1,1,false,false,1,1,1,1,1],array_fill(0,18,false))
];
for($i=count($samples);$i--;--$i)for($j=count($samples[$i]);$j--;)$samples[$i][$j]=!$samples[$i][$j];
while($samples)
{
    $a=array_shift($samples);
    $em=array_shift($samples);
    test($a,$em,$ym=s($a));
    $eu=[];foreach($em as$i=>$f)if($f)$eu[]=$a[$i];
    $yu=[];foreach($ym as$i=>$f)if($f)$yu[]=$a[$i];
#   sort($eu); sort($yu);
    test('unique values',$eu,$yu);
}
echo '</table>';

```
> 1 votes

# Answer
# C++, 242 bytes

Admittedly an overkill solution, as it works on *any* standard container of *any* ordered type:

```
#include<algorithm>
#include<list>
#include<set>
template<class T>auto f(T a){using V=typename T::value_type;std::set<V>s;std::list<bool>r;std::transform(a.begin(),a.end(),std::back_inserter(r),[&](V m){return s.insert(m).second;});return r;}

```

## Ungolfed:

(and further generalised)

```
template<class T>
auto f(T a)
{
    using std::begin;
    using std::end;
    using V=typename T::value_type;
    std::set<V>s;
    std::list<bool>r;
    std::transform(begin(a),end(a),std::back_inserter(r),[&](V m){return s.insert(m).second;});
    return r;
}

```

## Test suite:

```
int test(const std::list<bool>& expected, const auto& x) { return f(x) != expected; }
#include<array>
#include<chrono>
#include<forward_list>
#include<initializer_list>
#include<string>
#include<vector>
using namespace std::literals::chrono_literals;
int main()
{
    return 0
        + test({},            std::vector<short>{})
        + test({1},           std::array<int,1>{})
        + test({1},           std::vector<char>{55})
        + test({true,true},   std::vector<unsigned>{32,44})
        + test({1,0},         std::list<std::string>{"zero", "zero"})
        + test({1,0,0},       std::vector<long>{9001,9001,9001})
        + test({1,1,1,1},     std::array<char,4>{5,4,7,1})
        + test({1,1,1,1,0,1}, std::initializer_list<std::string>{"one","two","three","four","three","five"})
        + test({1,0,1,0,0},   std::forward_list<std::chrono::seconds>{60s, 1min, 3600s, 60min, 1h});
}

```
> 1 votes

# Answer
# TSQL 52 bytes

```
DECLARE @ TABLE(i int identity, v int)
INSERT @ values(1),(2),(3),(4),(3),(5)

SELECT i/max(i)over(partition by v)FROM @ ORDER BY i

```

**Fiddle**
> 1 votes

# Answer
# Perl 5 + Perligata, 343 bytes

315 bytes, plus 28 for `-MLingua::Romana::Perligata`

Use as `perl -MLingua::Romana::Perligata foo.pl`; input (from stdin) and output (to stdout) are underscore-separated strings of decimal integers. Tested on Strawberry 5.20.2 with version 0.6 of Perligata; I don't know whether it works with Perligata version 0.50.

```
huic vestibulo perlegementum da.qis _ scindementa da.dum qis fac sic
ao qis decumulamentum da.ao aum tum nullum addementum da.meo io.meo ro.per ium in qis fac sic
si ium tum aum aequalitas fac sic ro I da cis cis
ro nullum tum non rum addementum da.capita bis rum cis
per in bis fac sic hoc tum _ egresso scribe cis

```

---

Obviously this is clear as a bell. In case it's not, run it with `-MLingua::Romana::Perligata=converte` instead of `-MLingua::Romana::Perligata`, and `perl` will, instead of running the script, output a translation into regular Perl:

```
 $_ = Lingua::Romana::Perligata::getline (*STDIN );
 @q = split ( '_');
while (@q) { $a = pop (@q );
 $a =  ($a + 0);
my $i ;
my $r ;
for $i (@q) {if ( ($i eq $a)) { $r = 1}
}
;
 $r =  (0 +  ! ($r));
unshift (@b, $r)}
;
for $_ (@b) {print (STDOUT $_, '_')}

```

For a token-by-token analysis, use `-MLingua::Romana::Perligata=discribe`.

---

Golfing notes:

* Undocumented (but unsurprising), you don't need a space after `.`.
* (Also unsurprising,) `scinde` doesn't need a second argument, and uses `hoc`.
* I had to use `ao aum tum nullum addementum da` because I couldn't get `morde` to work.
* Similarly, I used `per ium in qis... ro I da` because I couldn't get `vanne` to work.
* Instead of `huic vestibulo perlegementum da`, I tried `-pMLingua::Romana::Perligata`, but couldn't get it to work, either.

---

Just for kicks (although this whole answer was just for kicks):

* After cleaning it up to `Huic vestibulo perlegementum da. Qis lacunam scindementa da. Dum qis fac sic ao qis decumulamentum da. Ao aum tum nullum addementum da. Meo io. Meo ro. Per ium in qis fac sic si ium tum aum aequalitas fac sic ro I da cis cis. Ro nullum tum non rum addementum da. Capita bis rum cis. Per in bis fac sic hoc tum lacunam egresso scribe cis.`, Google Translate gives `This court perlegementum grant. QIS gap scindementa grant. While QIS QIS decumulamentum do so ao da. Ao sum and no addementum grant. My io. My ro. Through ium in QIS do so if the sum ium equality do so ro 1 from cis. Ro was not any rum addementum grant. The heads of the bis side. Write, do so as soon as he at that time that in the gap by the Kish was taken.`.
> 1 votes

# Answer
# GolfScript, 19 bytes

```
..|:i;{i,\i\-:i,-}%

```

Explanation!

```
..|:i;{i,\i\-:i,-}% #Distinct sieve
..                  #Duplicate twice. Stack is [A A A]
  |                 #Binary OR. Removes duplicates. Stack is [A (A|A)]
   :i;              #Call this A|A i, and remove it from the stack. [A], i=A|A
      {          }% #Block notation. For each element in the top array, perform this on it.
      {i,        }% #Size of i. Element in array is [E (i,)].
      {  \       }% #Swap the top two elements. [(i,) E]
      {   i\     }% #Put i in the actual second position. [(i,) i E]
      {     -    }% #Remove all instances of the top element from the second. [(i,) (i-E)]
      {      :i  }% #This (i-E) is our new i (for the next loop).
      {        , }% #Size of topmost element (either i, or i,-1 if index was found).
      {         -}% #Subtract. This gives us 1 if E was removed from i, 0 otherwise.

```

Try it online!
> 1 votes

# Answer
# jq, 41 bytes

```
.[:range(length)+1]|[.[:-1][]!=.[-1]]|all

```

Try it online!

Takes an array, outputs a stream of jq booleans corresponding to its distinct sieve.

-10 from ovs.
> 1 votes

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