title: Counting generalized polyominoes

text:
# Question
Title: Counting generalized polyominoes
This challenge will have you count pseudo-polyforms on the snub square tiling.

I think that this sequence does not yet exist on the OEIS, so this challenge exists to compute as many terms as possible for this sequence.

*Update: this is now on the OEIS as A309159: Number of generalized polyforms on the snub square tiling with n cells.*

# Definitions

The snub square tiling is a semiregular tiling of the plane that consists of equilateral triangles and squares.

A pseudo-polyform on the snub square tiling is a plane figure constructed by joining together these triangles and squares along their shared sides, analogous to a polyomino. Here is an example of a six-cell and an eight-cell pseudo-polyform:

# Examples

For `n = 1` there are two 1-cell pseudo-polyforms, namely the square and the triangle:

For `n = 2` there are two 2-cell pseudo-polyforms, namely a square with a triangle and two triangles.

For `n = 3` there are four 3-cell pseudo-polyforms.

# Challenge

The goal of this challenge is to compute as many terms as possible in this sequence, which begins `2, 2, 4, ...` and where the n-th term is the number of n-cell pseudo-polyforms up to rotation and reflection.

Run your code for as long as you'd like. The winner of this challenge will be the user who posts the most terms of the sequence, along with their code. If two users post the same number of terms, then whoever posts their last term earliest wins.

(Once there are enough known terms to prove that this sequence does not already exist in the OEIS, I'll create an entry in the OEIS and list the contributor as a co-author if he or she desires.)

# Answer
> 7 votes
# Haskell

Now that not only the comments document that Peter Taylor was the first one to give enough terms to search on OEIS, I can give my results.

```
( 1 - 10) 2, 2, 4, 10, 28, 79, 235, 720, 2254, 7146,
(11 - 15) 22927, 74137, 241461, 790838, 2603210,
(16 - 18) 8604861, 28549166, 95027832,
(19 - 22) 317229779, 1061764660, 3562113987, 11976146355

```

Earlier, I counted hexagonal polyominoes. Except for some optimizations, what I'm doing here is very similar.

The elements of the tiling are represented like this: You can go in an almost straight line from left to right (in the first picture), alternating between squares and rectangles. There are almost parallel further lines, wiggling in opposite directions. Together, they miss some triangles. There are similar almost straight parallel lines from bottom to top, containing the missing triangles. Now ignore the wiggling and use a Cartesian coordinate system, but only use odd numbers for the coordinates of the squares. Then the triangles naturally get coordinate pairs with one even and one odd coordinate. Pairs with both coordinates even don't represent elements of the tiling.

(You could as well use even numbers for the coordinates of the squares. I guess I decided this way because I thought about reflection before rotation.)

Save the program in a file with a name like `cgp.hs` and compile with `ghc -O2 -o cgp cgp.hs`. It takes either one numeric command line argument and computes the number of polyominoes of that size, or none, in which case it computes values until stopped.

```
{-# LANGUAGE BangPatterns #-}

import Data.List(sort)
import qualified Data.Set as S
import System.Environment(getArgs)

data Point = P !Int !Int deriving (Eq,Ord)

start :: Point
start = P 1 1

redsq :: Point -> Bool
redsq (P x y) = (x+y) `mod` 4 == 2

neighs :: Point -> [Point]
neighs (P x y) =
  case (even x, even y) of
    (False,False) -> [P x (y+1), P (x+1) y, P x (y-1), P (x-1) y]
    (True, False) -> (P x (c y (x+y+1))) : opt [P (x-1) y, P (x+1) y]
    (False,True ) -> (P (c x (x+y-1)) y) : opt [P x (y-1), P x (y+1)]
  where
    opt = filter ok
    ok p = p>start || not (redsq p)
    c z m = if m `mod` 4 == 0 then z+2 else z-2

count :: S.Set Point -> S.Set Point -> [Point] -> Int -> Int -> Int -> Int -> Int
count use _    _            0 c r y =
  if check (S.toAscList use) (y==r)
    then c+1
    else c
count _   _    []           _ c _ _ = c
count use seen (p:possible) n c r y =
  let !c' = count use seen possible n c r y
      new = filter (`S.notMember` seen) $ neighs p
      !r' = if redsq p then r+1 else r
      !y' = if redsq (mirror p) then y+1 else y
      !n' = n-1
  in if r'+n' < y'
       then c'
       else count (S.insert p use) (foldr S.insert seen new) (new++possible)
                  n' c' r' y'

class Geom g where
  translate :: Int -> Int -> g -> g
  rot :: g -> g
  mirror :: g -> g

instance Geom Point where
  translate dx dy (P x y) = P (dx+x) (dy+y)
  rot (P x y) = P (2-y) x    -- rotate around (1,1)
  mirror (P x y) = P x (-y)

instance (Geom g, Ord g) => Geom [g] where
  translate x y = map $ translate x y
  rot = sort . map rot
  mirror = sort . map mirror

normalize :: [Point] -> [Point]
normalize pol = let (P x y) = head (filter redsq pol)
                in translate (1-x) (1-y) pol

check :: [Point] -> Bool -> Bool
check pol !cm = let rotated = take 4 $ iterate rot pol
                    mirrored = if cm then map mirror rotated else []
                    alts = map normalize (tail rotated ++ mirrored)
                in all (pol<=) alts

f :: Int -> Int
f 0 = 1; f 1 = 2; f 2 = 2
f n = count S.empty S.empty [start] n 0 0 0

output :: Int -> IO ()
output n = putStrLn $ show n ++ ": " ++ show (f n)

main = do args <- getArgs
          case args of
            []  -> mapM_ output [1..]
            [n] -> output (read n)

```

Try it online!

# Answer
> 6 votes
## 2, 2, 4, 10, 28, 79, 235, 720, 2254, 7146, 22927, 74137, 241461, 790838, 2603210, 8604861, 28549166, 95027832

I'm going to put a stake in the ground before Christian Sievers posts an answer for n=18. This is as far as I can go with the current code and 16GB of RAM. I've already had to sacrifice some speed to reduce the memory usage, and I'm going to have to do so even more. I have some ideas...

This snippet is the SVG from the first comment.

```
<svg xmlns="http://www.w3.org/2000/svg" width="130" height="130">
  <path style="stroke:none; fill:#f22" d="M 72,72 l -14.235,53.1259 -53.1259,-14.235 14.235,-53.1259 z" />  <!-- "Anticlockwise" square -->
  <path style="stroke:none; fill:#44f" d="M 72,72 l 53.1259,-14.235 -14.235,-53.1259 -53.1259,14.235 z" />  <!-- "Clockwise" square -->

  <path style="stroke:none; fill:#4f4" d="M 72,72 l 38.89,38.89 14.235,-53.1259 z" />  <!-- "NE" triangle -->
  <path style="stroke:none; fill:#ff4" d="M 72,72 l 38.89,38.89 -53.1259,14.235 z" />  <!-- "SW" triangle -->
  <path style="stroke:none; fill:#4ff" d="M 72,72 m -53.1259,-14.235 l 38.89,-38.89 -53.1259,-14.235 z" />  <!-- "NW" triangle -->

  <path style="stroke:#000; fill:none" d="M 72,72 m 38.89,38.89 l 14.235,-53.1259 -14.235,-53.1259 -53.1259,14.235 -53.1259,-14.235 14.235,53.1259 -14.235,53.1259 53.1259,14.235 53.1259,-14.235" />
</svg>
```

Code is C#. I ran it with .Net Core 2.2.6 under Linux.

```
#define SUPERLIGHT
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Sandbox
{
    // https://codegolf.stackexchange.com/questions/187763/counting-generalized-polyominoes
    // Count polyominos on the snub square tiling.

    // We index the tiles using the following basic element, which tiles like a square:
    /*
        <?xml version="1.0" standalone="no"?>
        <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
        <svg xmlns="http://www.w3.org/2000/svg" width="130" height="130">
            <path style="stroke:none; fill:#f22" d="M 72,72 l -14.235,53.1259 -53.1259,-14.235 14.235,-53.1259 z" />  <!-- "Anticlockwise" square -->
            <path style="stroke:none; fill:#44f" d="M 72,72 l 53.1259,-14.235 -14.235,-53.1259 -53.1259,14.235 z" />  <!-- "Clockwise" square -->

            <path style="stroke:none; fill:#4f4" d="M 72,72 l 38.89,38.89 14.235,-53.1259 z" />  <!-- "NE" triangle -->
            <path style="stroke:none; fill:#ff4" d="M 72,72 l 38.89,38.89 -53.1259,14.235 z" />  <!-- "SW" triangle -->
            <path style="stroke:none; fill:#4ff" d="M 72,72 m -53.1259,-14.235 l 38.89,-38.89 -53.1259,-14.235 z" />  <!-- "NW" triangle -->
            <!-- There's a "SE" triangle, but it's unfilled -->

            <path style="stroke:#000; fill:none" d="M 72,72 m 38.89,38.89 l 14.235,-53.1259 -14.235,-53.1259 -53.1259,14.235 -53.1259,-14.235 14.235,53.1259 -14.235,53.1259 53.1259,14.235 53.1259,-14.235" />
        </svg>
    */
    // In terms of symmetries, we have rotation by 90 degrees and reflection, possibly with glide.
    // We obviously want a canonical representation.
    //   Reflection interchanges "anticlockwise" and "clockwise" squares, so we shall require at least as many anticlockwise as clockwise.
    //   Rotation anticlockwise by 90 maps NE -> NW -> SW -> SE -> NE. We rotate to get a standard necklace.
    //   Further ties must be broken lexicographically, after translating to give minimum X and Y of 0.
    class PPCG187763
    {

        internal static void Main()
        {
            SanityChecks();

            var polyominos = new HashSet<TileSet>();
            polyominos.Add(new TileSet(Enumerable.Repeat(new Tile { X = 0, Y = 0, Shape = TileShape.SE }, 1)));
            polyominos.Add(new TileSet(Enumerable.Repeat(new Tile { X = 0, Y = 0, Shape = TileShape.Anticlockwise }, 1)));
            Console.WriteLine($"1\t{polyominos.Count}");
            for (int tileCount = 2; tileCount < 60; tileCount++)
            {
                var sw = new Stopwatch();
                sw.Start();
                var nextPolyominos = new HashSet<TileSet>();
                // TODO This can be greatly optimised by tracking discarded insertion points
                foreach (var polyomino in polyominos)
                {
                    foreach (var neighbour in polyomino.SelectMany(tile => tile.Neighbours).Distinct())
                    {
                        if (!polyomino.Contains(neighbour)) nextPolyominos.Add(new TileSet(polyomino.Concat(Enumerable.Repeat(neighbour, 1))));
                    }
                }
                polyominos = nextPolyominos;
                Console.WriteLine($"{tileCount}\t{polyominos.Count}\t{sw.ElapsedMilliseconds}ms");
            }
        }

        private static void SanityChecks()
        {
            var cluster = new HashSet<Tile>();
            cluster.Add(new Tile { Shape = TileShape.Anticlockwise });
            for (int i = 0; i < 3; i++)
            {
                foreach (var tile in cluster.SelectMany(tile => tile.Neighbours).ToList()) cluster.Add(tile);
            }

            foreach (var tile in cluster)
            {
                foreach (var neighbour in tile.Neighbours)
                {
                    if (!neighbour.Neighbours.Contains(tile))
                    {
                        throw new Exception("Assertion failed: adjacency isn't symmetric");
                    }

                    if (!tile.Flip().Neighbours.Contains(neighbour.Flip()))
                    {
                        throw new Exception("Assertion failed: flip doesn't preserve adjacency");
                    }

                    if (!tile.Rot().Neighbours.Contains(neighbour.Rot()))
                    {
                        throw new Exception("Assertion failed: rot doesn't preserve adjacency");
                    }

                    if (!tile.Equals(tile.Rot().Rot().Rot().Rot()))
                    {
                        throw new Exception("Assertion failed: rot^4 should be identity");
                    }
                }
            }
        }

        struct Tile : IComparable<Tile>
        {
            public TileShape Shape { get; set; }
            public sbyte X { get; set; }
            public sbyte Y { get; set; }

            public IEnumerable<Tile> Neighbours
            {
                get
                {
                    switch (Shape)
                    {
                        case TileShape.Anticlockwise:
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.SE };
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.SW };
                            yield return new Tile { X = X, Y = (sbyte)(Y - 1), Shape = TileShape.NW };
                            yield return new Tile { X = (sbyte)(X - 1), Y = Y, Shape = TileShape.NE };
                            break;

                        case TileShape.Clockwise:
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.SE };
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.NE };
                            yield return new Tile { X = X, Y = (sbyte)(Y + 1), Shape = TileShape.SW };
                            yield return new Tile { X = (sbyte)(X + 1), Y = Y, Shape = TileShape.NW };
                            break;

                        case TileShape.NE:
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.SW };
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.Clockwise };
                            yield return new Tile { X = (sbyte)(X + 1), Y = Y, Shape = TileShape.Anticlockwise };
                            break;

                        case TileShape.NW:
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.SE };
                            yield return new Tile { X = (sbyte)(X - 1), Y = Y, Shape = TileShape.Clockwise };
                            yield return new Tile { X = X, Y = (sbyte)(Y + 1), Shape = TileShape.Anticlockwise };
                            break;

                        case TileShape.SE:
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.NW };
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.Clockwise };
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.Anticlockwise };
                            break;

                        case TileShape.SW:
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.NE };
                            yield return new Tile { X = X, Y = (sbyte)(Y - 1), Shape = TileShape.Clockwise };
                            yield return new Tile { X = X, Y = Y, Shape = TileShape.Anticlockwise };
                            break;

                        default:
                            throw new NotSupportedException();
                    }
                }
            }

            public Tile Flip()
            {
                // We'll flip vertically.
                switch (Shape)
                {
                    case TileShape.Anticlockwise:
                        return new Tile { Shape = TileShape.Clockwise, X = X, Y = (sbyte)-Y };
                    case TileShape.Clockwise:
                        return new Tile { Shape = TileShape.Anticlockwise, X = (sbyte)(X + 1), Y = (sbyte)-Y };
                    case TileShape.NE: // G
                        return new Tile { Shape = TileShape.SE, X = (sbyte)(X + 1), Y = (sbyte)-Y };
                    case TileShape.NW: // Cy
                        return new Tile { Shape = TileShape.SW, X = X, Y = (sbyte)-Y };
                    case TileShape.SE: // W
                        return new Tile { Shape = TileShape.NE, X = X, Y = (sbyte)-Y };
                    case TileShape.SW: // Y
                        return new Tile { Shape = TileShape.NW, X = (sbyte)(X + 1), Y = (sbyte)-Y };
                    default:
                        throw new NotSupportedException();
                }
            }

            public Tile Rot()
            {
                // Anti-clockwise rotation: (x, y) = (-y, x)
                // But there will be offsets to account for the positions within the cell
                switch (Shape)
                {
                    case TileShape.Anticlockwise:
                        return new Tile { Shape = TileShape.Anticlockwise, X = (sbyte)-Y, Y = X };
                    case TileShape.Clockwise:
                        return new Tile { Shape = TileShape.Clockwise, X = (sbyte)(-Y - 1), Y = X };
                    case TileShape.NE:
                        return new Tile { Shape = TileShape.NW, X = (sbyte)-Y, Y = X };
                    case TileShape.NW:
                        return new Tile { Shape = TileShape.SW, X = (sbyte)(-Y - 1), Y = X };
                    case TileShape.SE:
                        return new Tile { Shape = TileShape.NE, X = (sbyte)(-Y - 1), Y = X };
                    case TileShape.SW:
                        return new Tile { Shape = TileShape.SE, X = (sbyte)-Y, Y = X };
                    default:
                        throw new NotSupportedException();
                }
            }

            public override int GetHashCode() => (X << 17) + (Y << 3) + (int)Shape;

            public bool Equals(Tile tile) => X == tile.X && Y == tile.Y && Shape == tile.Shape;

            public override bool Equals(object obj) => obj is Tile tile && Equals(tile);

            public int CompareTo(Tile other)
            {
                if (X != other.X) return X.CompareTo(other.X);
                if (Y != other.Y) return Y.CompareTo(other.Y);
                return Shape.CompareTo(other.Shape);
            }

            public override string ToString() => $"({X},{Y},{Shape})";
        }

        enum TileShape : byte
        {
            Anticlockwise,
            Clockwise,
            NE,
            SW,
            NW,
            SE
        }

        class TileSet : IReadOnlyCollection<Tile>
        {
            public TileSet(IEnumerable<Tile> tiles)
            {
                // Canonicalise
                var ordered = _Canonicalise(new HashSet<Tile>(tiles));
                int h = 1;
                foreach (var tile in ordered) h = h * 37 + tile.GetHashCode();
                _HashCode = h;

                #if SUPERLIGHT

                // Since we normalise to have minimum X and Y of 0, we can use unsigned coordinates.
                // And since we're looking at connected graphs of on the order of 20 items, 6 bits per coordinate is plenty.
                _Items = ordered.Select(tile => (short)((tile.X << 9) + (tile.Y << 3) + (int)tile.Shape)).ToArray();

                #else

                _Items = new HashSet<Tile>(ordered);

                #endif
            }

            private IReadOnlyList<Tile> _Canonicalise(ISet<Tile> tiles)
            {
                int ac = tiles.Count(tile => tile.Shape == TileShape.Anticlockwise);
                int c = tiles.Count(tile => tile.Shape == TileShape.Clockwise);

                if (ac < c) return _CanonicaliseRot(tiles);
                if (ac > c) return _CanonicaliseRot(tiles.Select(tile => tile.Flip()));

                return _Min(_CanonicaliseRot(tiles), _CanonicaliseRot(tiles.Select(tile => tile.Flip())));
            }

            private IReadOnlyList<Tile> _Min(IReadOnlyList<Tile> tiles1, IReadOnlyList<Tile> tiles2)
            {
                for (int i = 0; i < tiles1.Count; i++)
                {
                    int cmp = tiles1[i].CompareTo(tiles2[i]);
                    if (cmp < 0) return tiles1;
                    if (cmp > 0) return tiles2;
                }

                return tiles1;
            }

            private IReadOnlyList<Tile> _CanonicaliseRot(IEnumerable<Tile> tiles)
            {
                //   Rotation anticlockwise by 90 maps NE -> NW -> SW -> SE -> NE. We rotate to get one of these necklaces (in rank order, not exact values):
                //     Necklaces:
                //     SE NE NW SW
                //     0  0  0  0    ** Four positions to consider
                //     1  0  0  0
                //     1  0  1  0    ** Two positions to consider
                //     1  1  0  0
                //     1  1  1  0
                //     2  0  0  1
                //     2  0  1  0
                //     2  0  1  1
                //     2  1  0  0
                //     2  1  0  1
                //     2  1  1  0
                //     2  1  2  0
                //     2  2  0  1
                //     2  2  1  0
                //     3  0  1  2
                //     3  0  2  1
                //     3  1  0  2
                //     3  1  2  0
                //     3  2  0  1
                //     3  2  1  0

                int se = tiles.Count(tile => tile.Shape == TileShape.SE);
                int ne = tiles.Count(tile => tile.Shape == TileShape.NE);
                int nw = tiles.Count(tile => tile.Shape == TileShape.NW);
                int sw = tiles.Count(tile => tile.Shape == TileShape.SW);
                var sorted = new int[] { se, ne, nw, sw }.Distinct().OrderBy(x => x);
                var index = 1000 * sorted.IndexOf(se) + 100 * sorted.IndexOf(ne) + 10 * sorted.IndexOf(nw) + sorted.IndexOf(sw);
                switch (index)
                {
                    case 0:
                        // All four positions need to be considered
                        var best = _Translate(tiles);
                        best = _Min(best, _Translate(tiles.Select(tile => tile.Rot())));
                        best = _Min(best, _Translate(tiles.Select(tile => tile.Rot().Rot())));
                        best = _Min(best, _Translate(tiles.Select(tile => tile.Rot().Rot().Rot())));
                        return best;

                    case 101:
                        // Two options need to be considered;
                        return _Min(_Translate(tiles.Select(tile => tile.Rot())), _Translate(tiles.Select(tile => tile.Rot().Rot().Rot())));

                    case 1010:
                        // Two options need to be considered;
                        return _Min(_Translate(tiles), _Translate(tiles.Select(tile => tile.Rot().Rot())));

                    case 1000:
                    case 1100:
                    case 1110:
                    case 2001:
                    case 2010:
                    case 2011:
                    case 2100:
                    case 2101:
                    case 2110:
                    case 2120:
                    case 2201:
                    case 2210:
                    case 3012:
                    case 3021:
                    case 3102:
                    case 3120:
                    case 3201:
                    case 3210:
                        // Already in the canonical rotation.
                        return _Translate(tiles);

                    case    1:
                    case 1001:
                    case 1101:
                    case   12:
                    case  102:
                    case  112:
                    case 1002:
                    case 1012:
                    case 1102:
                    case 1202:
                    case 2012:
                    case 2102:
                    case  123:
                    case  213:
                    case 1023:
                    case 1203:
                    case 2013:
                    case 2103:
                        // Needs one rotation.
                        return _Translate(tiles.Select(tile => tile.Rot()));

                    case   10:
                    case   11:
                    case 1011:
                    case  120:
                    case 1020:
                    case 1120:
                    case   21:
                    case  121:
                    case 1021:
                    case 2021:
                    case  122:
                    case 1022:
                    case 1230:
                    case 2130:
                    case  231:
                    case 2031:
                    case  132:
                    case 1032:
                        // Needs two rotations.
                        return _Translate(tiles.Select(tile => tile.Rot().Rot()));

                    case  100:
                    case  110:
                    case  111:
                    case 1200:
                    case  201:
                    case 1201:
                    case  210:
                    case 1210:
                    case  211:
                    case  212:
                    case 1220:
                    case  221:
                    case 2301:
                    case 1302:
                    case 2310:
                    case  312:
                    case 1320:
                    case  321:
                        // Needs three rotations.
                        return _Translate(tiles.Select(tile => tile.Rot().Rot().Rot()));

                    default:
                        throw new NotSupportedException("Case analysis failed");
                }
            }

            private IReadOnlyList<Tile> _Translate(IEnumerable<Tile> tiles)
            {
                int minX = tiles.Min(tile => tile.X);
                int minY = tiles.Min(tile => tile.Y);
                return tiles.
                    Select(tile => new Tile { Shape = tile.Shape, X = (sbyte)(tile.X - minX), Y = (sbyte)(tile.Y - minY) }).
                    OrderBy(tile => tile).
                    ToList();
            }

            #if SUPERLIGHT

            private readonly short[] _Items;

            public int Count => _Items.Length;

            public IEnumerator<Tile> GetEnumerator()
            {
                foreach (var encoded in _Items)
                {
                    yield return new Tile { X = (sbyte)((encoded >> 9) & 0x3f), Y = (sbyte)((encoded >> 3) & 0x3f), Shape = (TileShape)(encoded & 0x7) };
                }
            }

            #else

            private readonly ISet<Tile> _Items;

            public int Count => _Items.Count;

            public IEnumerator<Tile> GetEnumerator() => _Items.GetEnumerator();

            public bool Contains(Tile tile) => _Items.Contains(tile);

            #endif

            IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

            private readonly int _HashCode;
            public override int GetHashCode() => _HashCode;

            public bool Equals(TileSet tileset) => tileset != null && tileset.Count == Count && tileset._HashCode == _HashCode && _Items.SequenceEqual(tileset._Items);

            public override bool Equals(object obj) => obj is TileSet tileset && Equals(tileset);
        }
    }

    static class Extensions
    {
        internal static int IndexOf<T>(this IEnumerable<T> elts, T elt)
            where T : IEquatable<T>
        {
            int idx = 0;
            foreach (var item in elts)
            {
                if (item.Equals(elt)) return idx;
                idx++;
            }
            return -1;
        }
    }
}

```

---
Tags: code-challenge, sequence, geometry, combinatorics, polyomino
---


# Question
Title: Construct a pentagon avoiding compass use
## Rules

You will start with only two elements: Points \\$A\\$ and \\$B\\$ such that \\$A \neq B\\$. These points occupy a plane that is infinite in all directions.

At any step in the process you may do any of the three following actions:

1. Draw a line that passes through two points.
2. Draw a circle centered at one point such that another point lies on the circle.
3. Add a new point where two objects (lines and circles) intersect.

Your goal is to create 5 points such that they form the vertices of a regular pentagon (a convex polygon with 5 sides equal in length) using as few circles as possible. You may, of course, have other points but 5 of them must for a regular pentagon. You do not have to draw the edges of the pentagon for your scoring.

## Scoring

When comparing two answers the one that draws fewer circles is better. In the case of a tie in circles the answer that draws the fewest lines is better. In the case of a tie in both circles and lines the answer that adds the fewest points is better.

## Anti-Rules

*While the rules list is exhaustive and details everything you can do, this list is not. Just because I don't say you can't do something does not mean you can.*

* You cannot create "arbitrary" objects. Some constructions you will find will do things like add a point at an "arbitrary" location and work from there. You cannot add new points at locations other than intersections.
* You cannot copy a radius. Some constructions will involve taking a compass setting it to a radius between two points and then picking it up and drawing a circle elsewhere. You cannot do this.
* You cannot perform limiting processes. All constructions must take a finite number of steps. It is not good enough to approach the answer asymptotically.
* You cannot draw an arc or part of a circle in order to avoid counting it as a circle in your scoring. If you want to visually use arcs when showing or explaining your answer because they take up less space go ahead but they count as a circle for scoring.

## Tools

You can think through the problem on GeoGebra. Just go over to the shapes tab. The three rules are equivalent to the point, line and circle with center tools.

## Burden of Proof

This is standard but I would like to reiterate. If there is a question as to whether a particular answer is valid the burden of proof is on the answerer to show that their answer is valid rather than the public to show that the answer is not.

## What is this doing on my Code-Golf site?!

This is a form of similar to albeit in a bit of a weird programming language. There is currently a +22/-0 consensus on the meta that this sort of thing is allowed.

# Answer
> 46 votes
# 2 circles, 13 lines, 17 points

Try it on GeoGebra

* Let circle(A, B) intersect circle(B, A) at C and D.
* Let AB intersect circle(A, B) again at E.
* Let AB intersect circle(B, A) again at F.
* Let AD intersect circle(A, B) again at G.
* Let AD intersect CF at H.
* Let BG intersect DF at I.
* Let HI intersect circle(A, B) at J and K.
* Let BG intersect EJ at L.
* Let BJ intersect EG at M.
* Let BG intersect EK at N.
* Let BK intersect EG at O.
* Let LM intersect circle(A, B) at P and S.
* Let NO intersect circle(A, B) at Q and R.

Then EPQRS is a regular pentagon.

### Why it works

Let BE intersect GJ at T, and let BE intersect GK at U. The complete quadrilateral BEGJ shows that T is the polar of LM, which is the intersection of the tangents at P and S. Similarly, the complete quadrilateral BEGK shows that U is the polar of NO, which is the intersection of the tangents at Q and R.

Let FG intersect HI at V. The diagonals DV and GI of the complete quadrilateral DGVI intersect FH at harmonic conjugates with respect to F and H; since the first is at ∞, the second is the midpoint C of FH, which is to say that C, D, V are collinear.

Let CG intersect HI at W.

Now for the fun part. Line FUBAT is perspective about G to line VKIHJ, which is perspective about D to circle CKDGJ, which is perspective about C to line HKVWJ, which is perspective about G to line AUF∞T. Composing these four perspecitivities yields a projectivity FUBAT ⌅ AUF∞T. Since a one-dimensional projectivity is determined by three points, T and U are determined as the two fixed points of FBA ⌅ AF∞.

Assigning coordinates with A = 0, B = −1, F = −2, this projectivity is defined by *x* ↦ 4/*x* \+ 2, and its fixed points T = 1 + √5 = sec(2π/5) and U = 1 − √5 = −sec(2π/10), exactly as required to make EPQRS a regular pentagon.

# Answer
> 17 votes
# ~~7~~ 6 circles, 3 lines

This is a classical pentagon construction, a proof of its correctness can be found here.

# Answer
> 13 votes
# 4 circles, 7 lines

Since it has been beaten I thought I would just post my original solution to the problem. This solution is modified from the method given by Dixon in *Mathographics*, a proof of correctness for that method can be found here.

* Draw \\$\mathrm{Circle}(A,B)\\$
* Draw \\$\overline{AB}\\$
* Mark the intersection of \\$\mathrm{Circle}(A,B)\\$ and \\$\overline{AB}\\$ as \\$C\\$
* Draw \\$\mathrm{Circle}(B,C)\\$
* Draw \\$\mathrm{Circle}(C,B)\\$
* Mark the intersection of \\$\mathrm{Circle}(C,B)\\$ and \\$\mathrm{Circle}(B,C)\\$ as \\$D\\$
* Mark the intersection of \\$\mathrm{Circle}(C,B)\\$ and \\$\overline{AB}\\$ as \\$E\\$
* Draw \\$\overline{DC}\\$
* Mark the intersection of \\$\mathrm{Circle}(C,B)\\$ and \\$\overline{DC}\\$ as \\$F\\$
* Mark the intersection of \\$\mathrm{Circle}(C,B)\\$ and \\$\mathrm{Circle}(B,C)\\$ as \\$G\\$
* Draw \\$\overline{BG}\\$
* Mark the intersection of \\$\overline{BG}\\$ and \\$\overline{EF}\\$ as \\$H\\$
* Draw \\$\overline{HC}\\$
* Mark the intersection of \\$\overline{HC}\\$ and \\$\mathrm{Circle}(C,B)\\$ as \\$I\\$
* Draw \\$\overline{IA}\\$
* Mark the intersection of \\$\overline{IA}\\$ and \\$\mathrm{Circle}(A,B)\\$ as \\$J\\$
* Draw \\$\mathrm{Cirlce}(I,J)\\$
* Mark the intersection of \\$\mathrm{Circle}(I,J)\\$ and \\$\overline{HC}\\$ as \\$L\\$
* Mark the intersections of \\$\mathrm{Circle}(I,J)\\$ and \\$\mathrm{Circle}(C,B)\\$ as \\$M\\$ and \\$K\\$.
* Draw \\$\overline{ML}\\$
* Draw \\$\overline{KL}\\$
* Mark the intersection of \\$\mathrm{Circle}(C,B)\\$ and \\$\overline{ML}\\$ as \\$N\\$
* Mark the intersection of \\$\mathrm{Circle}(C,B)\\$ and \\$\overline{HC}\\$ as \\$O\\$
* Mark the intersection of \\$\mathrm{Circle}(C,B)\\$ and \\$\overline{KL}\\$ as \\$P\\$

\\$MKPON\\$ is a regular pentagon.

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


title: How long's left?

text:
# Question
Title: How long's left?
# How long's left?

Recently, I was making pizza using a 5-minute timer on my phone. When someone walked in and asked me how long was left, I was confused for a moment at first as to how to answer the question. You see, if the timer at the current moment was at 3:47, by the time I had read out 'Three minutes and forty seven seconds' aloud, the time would have changed. Therefore, I need to find a time that the timer would reach *just* as I finish reading it out.

This is your challenge: to automate this process. Given a time in any appropriate format (":" delimited, or as a minute and second argument), output the earliest time from that current moment which would take an equal amount of time to read out as it would take for the timer to get to. We're assuming that each syllable takes 1 second to read out.

## Further rules

* You must count 'minutes' and 'seconds' as two of the syllables each, as well as an 'and' between them.
* The pizza will never take more than 59:59 to cook.
* '11 minutes and 0 seconds' is not 10 syllables: you must simplify to '11 minutes' (i.e 5 syllables). Same goes with minutes: '0 minutes and 7 seconds' is also only counted as 4 syllables.
* Your program can give the output in any format: an array of `[minutes, seconds]`, or even as `<minutes> minutes and <seconds> seconds` (normal text written out).
* Standard loopholes apply.
* This is , so shortest answer in bytes wins.

# Test cases

All inputs as `(minutes, seconds)`

```
(4, 47) = (4, 38) (Four MiNutes And ThirTy Eight SeConds - 9 syllables/seconds)
(1, 1) = (0, 56) (FifTy-Six SeConds - 5 syllables/seconds)
(59, 57) = (59, 46) (FifTy Nine Minutes And Forty Six SeConds - 11 syllables/seconds)
(0, 10) = null/error/0 (no positive answer)

```

# Syllable count reference

For reference, here are the number of syllables in each number up to 59.

```
0,0 (does not need to be counted)
1,1
2,1
3,1
4,1
5,1
6,1
7,2
8,1
9,1
10,1
11,3
12,1
13,2
14,2
15,2
16,2
17,3
18,2
19,2
20,2
21,3
22,3
23,3
24,3
25,3
26,3
27,4
28,3
29,3
30,2
31,3
32,3
33,3
34,3
35,3
36,3
37,4
38,3
39,3
40,2
41,3
42,3
43,3
44,3
45,3
46,3
47,4
48,3
49,3
50,2
51,3
52,3
53,3
54,3
55,3
56,3
57,4
58,3
59,3

```

# Answer
# JavaScript (ES6),  ~~112 106~~  105 bytes

*A shorter version based on a suggestion by @EmbodimentofIgnorance<br>6 more bytes saved by @DaniilTutubalin*

Takes input as `(minutes)(seconds)`. Returns `[minutes, seconds]` or \\$0\\$ if there's no solution.

```
m=>d=F=s=>m|s?(g=n=>n&&(n%10!=7)-7+(n-11?n<13?2:n<21|n%10<1:0))(m)+g(s)^~d?F(s?s-1:m--&&59,d=-~d):[m,s]:0

```

Try it online!

---

# JavaScript (ES6),  ~~126~~  119 bytes

Takes input as `(minutes)(seconds)`. Returns `[minutes, seconds]` or \\$0\\$ if there's no solution.

```
m=>d=F=s=>m|s?(g=n=>n&&2+(30774612>>2*n%(n>12?20:26)&3)+(n>12)+(n>19))(m)+g(s)+!!(m*s)^d?F(s?s-1:m--&&59,d=-~d):[m,s]:0

```

Try it online!

### Commented

```
m =>                  // m = minutes
d =                   // d = delta in seconds between the initial time and the current time,
                      //     initialized to a non-numeric value (zero-ish)
F = s =>              // F is a recursive function taking s = seconds
  m | s ? (           // if either m or s is not 0:
    g = n =>          //   g is a helper function taking an integer n in [0..59]
      n &&            //     return 0 if n = 0
      2 + (           //     otherwise, start with 2 for either 'mi-nutes' or 'se-conds'
        30774612 >>   //     add the base number of syllables (0 to 3) corresponding to n
        2 * n %       //     using a bitmask of 13 entries x 2-bit:
                      //       12 11 10  9  8  7  6  5  4  3  2  1  0
                      //       01 11 01 01 01 10 01 01 01 01 01 01 00
        (n > 12 ? 20  //     using n MOD 10 if n is greater than 12
                : 26) //     or just n otherwise
        & 3           //     isolate the two least significant bits
      ) +             //
      (n > 12) +      //     add 1 syllable for '-teen' or '-ty' if n is greater than 12
      (n > 19)        //     add 1 more syllable for 'x-ty' if n is greater than 19
  )(m) +              //   invoke g for the minutes
  g(s) +              //   invoke g for the seconds
  !!(m * s)           //   add 1 syllable for 'and' if both m and s are non-zero
  ^ d ?               //   if the result is not equal to the delta:
    F(                //     otherwise, do a recursive call:
      s ? s - 1       //       decrement s if it's not 0,
        : m-- && 59,  //       or decrement m and restart with s = 59
      d = -~d         //       increment the delta
    )                 //     end of recursive call
  :                   //   else:
    [m, s]            //     success: return [m, s]
:                     // else:
  0                   //   failure: return 0

```
> 4 votes

# Answer
# Python 3, ~~287~~ 285 bytes

```
m=int(input())
s=int(input())
y=lambda w:3+(w[-1]=='7')-(w[-1]=='0')-(w[0]in'01')*(1+(w[0]=='0'))+(w=='11')-(w=='12')
z=lambda m,s:(2+y(f'{m:02d}'))*(m!=0)+(2+y(f'{s:02d}'))*(s!=0)+(m!=0!=s)
q=lambda t: (m-(t+60-s-1)//60,(s-t)%60)
print([q(t) for t in range(s+60*m) if z(*q(t))==t][0])

```

Try it online!

It's not a very clever solution - it's mostly striaghtforward. Takes ~~'m:s'~~ **m and s as separate inputs** ~~(doesn't need to be padded),~~ and outputs (m,s). Throws an error if there's no valid output.

The program relies heavily on implicitly casting booleans to 0 and 1. The first line takes input. The second line defines a lambda function y which gives the syllables in a number - it assumes a base of 3 syllables, then adds 1 if it ends in 7, subtracts 1 if it ends in 0, and subtracts 1 if it's in the 10's and 2 if it's in the single digits. Twelve and eleven are manually adjusted at the end. The third line is a lambda for the syllables in the whole expression. Finally, fourth line gives the time after t seconds. Fifth line is the output - it builds an array of all the times that satisfy the problem, and outputs the first one.

**EDIT 1:** Thanks to Matthew Anderson in the comments, 2 bytes were shaved off by taking the inputs separately.
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), 141 bytes

```
a=>b=>((a=Enumerable.Range(1,b+=a*60).Last(i=>new[]{i/60,i%60}.Sum(x=>x<1?0:(x%10==7?4:3)+(x==11?3:x<13?1:x<21|x%10<1?2:3))-1==b-i))/60,a%60)

```

Try it online!
> 1 votes

# Answer
# Jelly, 46 bytes

```
ḅḶbɗ60Ṛµ“÷ṢḣxE⁻Ṇ⁹ƬƝwɼỤṡl’ḃ4+2;0⁸ịS+ṬS$’)=JTị⁸Ḣ

```

Try it online!

A monadic link taking as its argument the time as `[minutes, seconds]` and returning the appropriate time to say as `[minutes, seconds]` or `[seconds]` if less than a minute.
> 1 votes

# Answer
# CJam, 102 bytes

```
60:X;q~\X*+:W_{;(__X%\X/{_196656821516111872\_A%K+e<_{(2*m>3&3.5+}{\;}?@}2*+i+\X*+_W=!2$0<-}g;_X%\X/S@

```

Try it online!

Just a boring old magic-number binary look-up-table, nothing to see here.
> 0 votes

---
Tags: code-golf, date, natural-language, text-processing
---


title: Recursive acronyms

text:
# Question
Title: Recursive acronyms
## Objective

*From Wikipedia :*

> A recursive acronym is an acronym that refers to itself in the expression for which it stands.

Your goal is to check if a string is a recursive acronym.

* The acronym is the first word
* Words are not case sensitive, separated with a single space.
* The given string does not contain any punctuation nor apostrophe.
* Only the first letter of each word can be part of the acronym.

You must also give the function words. For simplicity, every word can be considered as a function word.

## Example

```
f("RPM Package Manager")         =>     { true, [] }
f("Wine is not an emulator")     =>     { true, ["an"] }
f("GNU is not Unix")             =>     { true, ["is"] }
f("Golf is not an acronym")      =>     { false }
f("X is a valid acronym")        =>     { true, ["is","a","valid","acronym"] }

```

You can give a full program or a function.
The input string can be taken from STDIN or as a function argument.
Output result can be true/false, 0/1, yes/no...
The function words list (any format of list is valid) must be given *if and only if* this is a recursive acronym (even if the list is empty). You do not have to preserve capitalization of the function words.

## Winning criteria

This is a , shortest code wins.

# Answer
## GolfScript, ~~51~~ 50 chars

```
{32|}%" "/(1>\{.1<2$1<={;1>}{\}if}/{]!}{]`1" "@}if

```

It probably can be golfed further. Takes input on STDIN. The boolean is 0/1.

Test online

---

Explanation:

```
{32|}%      # change everything to lower-case
" "/        # splits the string by spaces
(1>         # takes the first word out and removes the first letter
\           # moves the list of remaining words in front of the acronym word
{           # for every word:
  .1<2$1<=    # compares the first letter of the word with
              # the next unmatched letter of the acronym
  {;1>}       # if they are the same, discard the word and the now-matched letter
  {\}         # otherwise store the word in the stack
  if          # NB. if all letters have been matched, the comparison comes out as false
}/
{]!}        # if there are still unmatched letters, return 0 (`!` non-empty list)
{]`1" "@}   # otherwise, return 1, and display the list of function words
if

```
> 7 votes

# Answer
## Regex, .NET flavour, 62 bytes

```
(?i)(?<=^\w(?<c>\w)*)( \k<c>(?<-c>)\w+| (?<w>\w+))*$(?(c)(?!))

```

You can test it here. If the input is a recursive acronym, this will yield a match, and capturing group `w` will contain all function words. If it isn't, then there will be no match.

This *does* preserve capitalisation of the function words (but matches case-insensitively).

Unfortunately, the tester doesn't display the entire stack of a named capturing group, but if you used it anywhere in .NET, the `w` group *would* contain all function words in order.

Here is a C# snippet to prove that:

```
var pattern = @"(?i)(?<=^\w(?<c>\w)*)( \k<c>(?<-c>)\w+| (?<w>\w+))*$(?(c)(?!))";
var input = new string[] {
    "RPM Package Manager",
    "Wine is not an emulator",
    "GNU is not Unix",
    "Golf is not an acronym",
    "X is a valid acronym"
};

var r = new Regex(pattern);
foreach (var str in input)
{
    var m = r.Match(str);
    Console.WriteLine(m.Success);
    for (int i = 0; i < m.Groups["w"].Captures.Count; ++i)
        Console.WriteLine(m.Groups["w"].Captures[i].Value);
}

```

Here is a quick explanation. I'm using .NET's balancing groups to build a stack of the acronym letters in the named group `c`, with this snippet

```
^\w(?<c>\w)*

```

The trick is that I need the second letter on top of the stack and the last one at the bottom. So I put all of this in a lookbehind that matches the position *after* the acronym. This helps, because .NET matches lookbehinds from right to left, so it encounters the last letter first.

Once I got that stack, I match the rest of the string word for word. Either the word begins with the letter on top of the acronym stack. In that case I pop that letter from the stack:

```
 \k<c>(?<-c>)\w+

```

Otherwise, I match the word anyway and push onto the `w` stack which will then contain all function words:

```
 (?<w>\w+)

```

At the end I make sure I reached the end of the string with `$` and also make sure that I've used up all letters from the acronym, by checking that the stack is empty:

```
(?(c)(?!))

```

Test it on ideone.
> 22 votes

# Answer
# Python (158, without regex)

It's not that I don't like regexes. It's that I don't know them.

```
def f(x):
 s=x.lower().split();w=list(s[0][1:]);s=s[1:];o=[]
 if not w:return 1,s
 [w.pop(0)if i[0]==w[0]else o.append(i)for i in s]
 return(0,)if w else(1,o)

```

Oh, I also had an ungolfed version:

```
def acronym(string):
    scentence = string.lower().split()
    word = scentence[0][1:]
    scentence = scentence[1:]
    over = []
    if not word: return 1, scentence
    for item in scentence:
        if item[0] == word[0]:
            word = word[1:]
        else:
            over.append(item)
    if word:
        return 0,
    return 1,over

```
> 11 votes

# Answer
# Python 2.7 - ~~131~~ 126 bytes

```
def f(s):
 s=s.lower().split();a,f=list(s[0]),[]
 for w in s:f+=0*a.pop(0)if a and w[0]==a[0]else[w]
 return(0,)if a else(1,f)

```

Makes a list of letters in the first word of the acronym. Then, for each word in the full string, get rid of the first element of that list we made if it is the same as the first letter of that word. Otherwise, add that word to the list of function words. To output, return `not a` (In python, any list other than the empty list is `True`-y, and the list is empty if it's a recursive acronym) and the list if `not a`.

Thanks to @ace for helping me fix an error/save some bytes.
> 5 votes

# Answer
# ECMAScript 6 (105 bytes):

```
f=s=>(r=(a=s.toUpperCase(i=1).split(' ')).map((w,c)=>c?a[0][i]==w[0]?(i++,''):w:''),a[0].length==i?1+r:0)

```

Enter the function in Firefox's browser console, and then just call the function, like this:

```
f('ABC Black Cats')     // 1,,
f('ABC is Black Cats')  // 1,IS,,
f('ABC Clapping Cats')  // 0

```
> 3 votes

# Answer
# Python - 154 characters

First ever code golf attempt. I'm thinking python isn't the best language for it, given all the long keywords. Also, I don't think this function is foolproof. It works for the OP's input, but I'm sure I could think up exceptions.

```
def f(s):
    w=s.lower().split();r=list(w[0]);return(True,[x for x in w if x[0]not in r])if len(r)==1 or[x for x in[y[0]for y in w]if x in r]==r else False

```
> 3 votes

# Answer
# Haskell - 287 bytes

Not the shortest entry (hey this is Haskell, what did you expect?), but still a lot a fun to write.

```
import Data.Char
import Data.List
f""w=map((,)False)w
f _[]=[]
f(a:as)(cs@(c:_):w)
 |toLower a==toLower c=(True,cs):f as w
 |True=(False,cs):f(a:as)w
g s=if(length$filter(fst)d)==length v
  then Just$map(snd)$snd$partition(fst)d
  else Nothing
 where
  w=words s
  v=head w
  d=f v w

```

Tested with

```
map (g) ["RPM Package Manager","Wine is not an emulator","GNU is not Unix","Golf is not an acronym","X is a valid acronym"]

```

Expected output

```
[Just [],Just ["an"],Just ["is"],Nothing,Just ["is","a","valid","acronym"]]

```

# Ungolfed

```
import Data.Char
import Data.List

f :: String -> [String] -> [(Bool, String)]
f "" w = map ((,) False) w
f _ [] = []
f (a:as) ((c:cs):w) | toLower a == toLower c = (True, c:cs) : f as w
                    | otherwise = (False, c:cs) : f (a:as) w

g :: String -> Maybe [String]
g s = if (length $ filter (fst) d) == (length v)
          then Just $ map (snd) $ snd $ partition (fst) d
          else Nothing
  where w = words s
        v = head w
        d = f v w

```
> 2 votes

# Answer
# JavaScript (ECMAScript 6) - 97 Characters

```
f=x=>(r=(a=x.toLowerCase(i=0).split(' ')).filter(y=>y[0]!=a[0][i]||i-i++),i==a[0].length?[1,r]:0)

```

**Tests:**

```
f("RPM Package Manager")
[1, []]

f("GNU is not Unix")
[1, ["is"]]

f("X is an acronym")
[1, ["is", "an", "acronym"]]

f("Golf is not an acronym")
0

f("Wine is not an emulator")
[1, ["an"]]

```
> 2 votes

# Answer
# Rebol - 133

```
f: func[s][w: next take s: split s" "y: collect[foreach n s[either n/1 = w/1[take w][keep n]]]reduce either/only w: empty? w[w y][w]]

```

Ungolfed:

```
f: func [s] [
    w: next take s: split s " "
    y: collect [
        foreach n s [
            either n/1 = w/1 [take w][keep n]
        ]
    ]
    reduce either/only w: empty? w [w y][w]
]

```

Tested with:

```
foreach t [
    "RPM Package Manager"  "Wine is not an emulator"
    "GNU is not Unix"      "Golf is not an acronym"
    "X is a valid acronym"
][probe f t]

```

Output:

```
[true []]
[true ["an"]]
[true ["is"]]
[false]
[true ["is" "a" "valid" "acronym"]]

```
> 1 votes

# Answer
# Julia - 116 bytes

```
f(w)=(a=split(lowercase(w));L=1;A=a[];while a!=[];a[][1]==A[1]?A=A[2:]:(L=[L,a[]]);a=a[2:];A>""||return [L,a];end;0)

```

Less Golfed:

```
f(w)=(
 a=split(lowercase(w))
 L=1
 A=a[]
 while a!=[]
  if a[][1]==A[1]
   A=A[2:]
  else
   L=[L,a[]]
  end
  a=a[2:]
  if !(A>"")
   return [L,a]
  end
 end
0)

```

The `0` on the end makes it output 0. Otherwise, it outputs an array containing `1` followed by the function words. For example:

```
julia> f("RPM Package Manager")
1-element Array{Any,1}:
 1

julia> f("Golf is not an acronym")
0

julia> f("GNU is not Unix")
2-element Array{Any,1}:
 1
  "is"

julia> f("X is a valid acronym")
5-element Array{Any,1}:
 1
  "is"
  "a"
  "valid"
  "acronym"

```
> 1 votes

# Answer
# Brachylog, 29 bytes

```
ḷṇ₁XhY∧X;0zpᵐz{ċ₂ˢ}ᵐZhhᵐcY∧Zt

```

Try it online!

Outputs the function words through the output variable if the input is a recursive acronym, and fails if it is not.

```
   X                             X is
ḷ                                the input lowercased
 ṇ₁                              and split on spaces,
    hY                           the first element of which is Y
      ∧                          (which is not X).
       X  z                      X zipped
        ;0                       with zero,
           pᵐ                    with all pairs permuted (creating a choicepoint),
             z                   zipped back,
              {   }ᵐ             and with both resulting lists
               ċ₂ˢ               losing all non-string elements,
                    Z            is Z.
                      hᵐ         The first elements of the elements of
                    Zh           the first element of Z
                        cY       concatenated are Y
                          ∧      (which is not Z).
                           Zt    The last element of Z is the output.

```

Without having to output the function words (treating this as a pure ), it comes out to just 12 bytes, because `∧Zt` can be dropped for -3, `Y` can be replaced with `.` for -1, and most importantly `;0zpᵐz{ċ₂ˢ}ᵐZh` can be replaced with  for a whopping -13: `ḷṇ₁Xh.∧X⊇hᵐc`
> 1 votes

# Answer
# Cobra - 187

```
def f(s as String)
    l=List<of String>(s.split)
    a=l[0]
    l.reverse
    o=0
    for c in a,for w in l.reversed
        if c==w[0]
            l.pop
            o+=1
            break
    x=o==a.length
    print x,if(x,l,'')

```
> 0 votes

# Answer
## Java - 195

Unfortunately, Java does not have built in tuple support.

So, this is a class that stores the boolean in 'b' and the function word list in 'x'.

Here, the function is the constructor of the class.

```
static class R{boolean b;String[]x;R(String s){String v=" ",i="(?i)",f=s.split(v)[0],r=i+f.replaceAll("(?<=.)",".* ");if(b=(s+=v).matches(r))x=(s.replaceAll(i+"\\b["+f+"]\\S* ","")+v).split(v);}}

```

Test

```
public class RecursiveAcronyms {
public static void main(String args[]) {
    String[] tests = {
            "RPM Package Manager",
            "Wine is not an emulator",
            "GNU is not Unix",
            "Golf is not an acronym",
            "X is a valid acronym"
        };
    for (String test:tests) {
        R r = new R(test);
        System.out.print(r.b);
        if (r.b) for (String s:r.x) System.out.print(" "+s);
        System.out.print("\n");
    }
}
static class R{boolean b;String[]x;R(String s){String v=" ",i="(?i)",f=s.split(v)[0],r=i+f.replaceAll("(?<=.)",".* ");if(b=(s+=v).matches(r))x=(s.replaceAll(i+"\\b["+f+"]\\S* ","")+v).split(v);}}}

```
> 0 votes

# Answer
# Ruby - 173

Could be better...

```
 f=->s{a=[];o={};s=s.split;r=true;s[0].each_char{|c|s.each{|w| w[0]=~/#{c}/i?(o[c]=1;a<<w if o[c]):(o[c]=0 if !o[c])}};r,a=false,s if o.values&[0]==[0];!r ?[r]:[r,(s-(a&a))]}

```

Calling the func :

```
p f.call('RPM Package Manager')
p f.call('Wine is not an emulator')
p f.call("GNU is not Unix")
p f.call("Golf is not an acronym")
p f.call("X is a valid acronym")

```

Output :

```
[true, []]
[true, ["an"]]
[true, ["is"]]
[false]
[true, ["is", "a", "valid", "acronym"]]

```
> 0 votes

# Answer
# Awk - 145

```
awk -v RS=' ' '{c=tolower($0)};NR==1{w=c};{t=substr(c,1,1)!=substr(w,NR-s,1);if(t){f=f" "c;s++};a=a||t};END{print a&&(s>NR-length(w))?"N":"Y|"f}'

```

Test:

```
$ cat gcp.sh
#!/bin/sh
f() {
echo "$1:"
echo "$1"|awk -v RS=' ' '{c=tolower($0)};NR==1{w=c};{t=substr(c,1,1)!=substr(w,NR-s,1);if(t){f=f" "c;s++};a=a||t};END{print a&&(s>NR-length(w))?"N":"Y|"f}'
}
f "RPM Package Manager"
f "Wine is not an emulator"
f "Wine is not an appropriate emulator"
f "GNU is not Unix"
f "Golf is not an acronym"
f "Go is not an acronym"
f "Go is a valid acronym OK"
f "X is a valid acronym"
f "YAML Ain't Markup Language"

$ ./gcp.sh
RPM Package Manager:
Y|
Wine is not an emulator:
Y| an
Wine is not an appropriate emulator:
Y| an appropriate
GNU is not Unix:
Y| is
Golf is not an acronym:
N
Go is not an acronym:
N
Go is a valid acronym OK:
Y| is a valid acronym
X is a valid acronym:
Y| is a valid acronym

YAML Ain't Markup Language:
Y|

```
> 0 votes

# Answer
# Coffeescript - 144

```
z=(a)->g=" ";b=a.split g;c=b[0];d=[];(d.push(e);g++)for e,f in b when e[0].toLowerCase()!=c[f-g].toLowerCase();if(g+c.length==f)then{1,d}else{0}

```

Call it with, for instance: `z "GNU is not Unix"`

The compiled JS:

```
var z;
z = function(a) {
  var b, c, d, e, f, g, _i, _len;
  g = " ";
  b = a.split(g);
  c = b[0];
  d = [];
  for (f = _i = 0, _len = b.length; _i < _len; f = ++_i) {
    e = b[f];
    if (e[0].toLowerCase() !== c[f - g].toLowerCase()) {
      d.push(e);
      g++;
    }
  }
  if (g + c.length === f) {
    return {
      1: 1,
      d: d
    };
  } else {
    return {
      0: 0
    };
  }
};

```

It splits the string into words and then loops through each word. If the first character of the word doesn't match the next in the acronym, the word is stored. A counter (`g`) is used to track how many words have been skipped. If the number of skipped words plus the length of the acronym matches the length of the phrase, it matched, so return 1 and the skipped words. If not, it was not valid, so return 0.
> 0 votes

# Answer
# C# - 234

```
Tuple<bool,string[]> f(string w) {var l=w.ToLower().Split(' ');var o=new List<string>();int n=0;var a=l[0];foreach(var t in l){if(n>=a.Length||a[n]!=t[0])o.Add(t);else n++;}var r=n>=a.Length;return Tuple.Create(r,r?o.ToArray():null);}

```
> 0 votes

# Answer
# Python (108)

```
l=raw_input().lower().split()
a=l[0]
e=[]
for w in l:d=w[0]!=a[0];a=a[1-d:];e+=[w]*d
b=a==''
print b,b*`e`

```
> 0 votes

---
Tags: code-golf
---


title: Simulate an instant runoff election

text:
# Question
Title: Simulate an instant runoff election
It's the election! The area which we are in implements the system of voting called **instant runoff** (sometimes called **alternative vote** or **preferential voting**). Each voter orders each candidate from most preferred to least preferred, marking a "1" for their most preferred candidate, a "2" for their second candidate, and so forth until each candidate is numbered. I'll let this friendly koala explain the rest:

<sup>(Image modified from original by Patrick Alexander, used under the CC BY-NC-SA 3.0 AU licence). </sup>

If you prefer your instant runoff explanation in text form, there's also the Wikipedia article.

(Note: It's also possible, although unlikely, for there to be two or more candidates with the least votes. In these situations, choose one of them randomly at equal probabilities and eliminate them.)

In this challenge, the first line of input is a list of strings, which are the names of the candidates for the election. In these examples I've used pipe delimited values, although feel free to adjust the input format to suit your language.

```
The Omitted Anti-neutrino|Placazoa|Alexander the Awesome|Tau Not Two|Semolina Sorcerer

```

Following that are `n` lines of input which are also lists of strings, each which represents a single vote. The first entry represents that votes #1 preference, the next the #2 preference, etc. For example:

```
Alexander the Awesome|Semolina Sorcerer|Tau Not Two|Placazoa|The Omitted Anti-neutrino

```

would mean that that particular vote has Alexander as their first preference, Semolina Sorcerer as their second, Tau Not Two as their third, etc. You can assume that every vote will contain every candidate, and that there will be no blank or incomplete votes.

Given the votes as input, your program or function should then output the winner of the election. You can find an ungolfed reference implementation in Python 3 here.

**Example Inputs and Outputs**

**Input**

```
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Alexander the Awesome|Dionysius|Red Trainmen
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Portal Butter|Red Trainmen|Alexander the Awesome|Dionysius
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Portal Butter|Dionysius
Red Trainmen|Alexander the Awesome|Dionysius|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Red Trainmen|Dionysius|Portal Butter|Alexander the Awesome
Alexander the Awesome|Dionysius|Red Trainmen|Portal Butter
Dionysius|Portal Butter|Alexander the Awesome|Red Trainmen
Alexander the Awesome|Red Trainmen|Dionysius|Portal Butter

```

**Output**

```
Alexander the Awesome

```

**Input**

```
Depressed Billy|Sighted Citrus|Frosty Fox|Electronic Accident
Frosty Fox|Sighted Citrus|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Depressed Billy|Sighted Citrus|Electronic Accident|Frosty Fox
Depressed Billy|Electronic Accident|Sighted Citrus|Frosty Fox
Electronic Accident|Frosty Fox|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Electronic Accident|Depressed Billy
Frosty Fox|Depressed Billy|Sighted Citrus|Electronic Accident
Sighted Citrus|Electronic Accident|Frosty Fox|Depressed Billy
Frosty Fox|Electronic Accident|Depressed Billy|Sighted Citrus
Sighted Citrus|Frosty Fox|Depressed Billy|Electronic Accident

```

**Output**

`Sighted Citrus` or `Frosty Fox` (randomly)

**Input**

You can get the last input set here. It is one of the voting areas of a recent Australian election, and consists of 63 428 votes.

**Output**

```
Ross HART

```

# Answer
# Pyth - 30 bytes

Will refactor it. Infers first line from rest of input.

```
WgclQ2leKlD.gkhMQ=Q-RhhJKQ;hhJ

```

Test Suite.
> 3 votes

# Answer
# , ~~101~~ 99 bytes

```
f=function(m)`if`(n<-dim(m)-1,f(matrix(m[m!=names(t<-sample(table(m[1,])))[which.min(t)]],n)),m[1])

```

Try it online!

Takes input as a matrix, with each column representing the choices of one voter. Works by recursion: find a candidate with minimal number of votes, delete all corresponding entries in the matrix, reformat the matrix, and recurse until the matrix has only 1 row.

The votes at each iteration are computed by counting with `table` the values in the top row, which are the current top choices of each voter. This is shuffled with `sample` to break ties at random.

`n<-dim(m)-1` gives a vector of length 2, but only the first value is used (so it is equivalent, but 1 byte shorter than, `n<-nrow(m)-1`). This value is used twice: first it is compared to 0 to check whether the last iteration has been reached; second, if we recurse, it is the number of rows of the new matrix.
> 1 votes

# Answer
# Python 2, 209 bytes

```
def f(s):
 d={}
 for v in s:
	k=v[0];d[k]=d.get(k,[])+[v]
	if len(d[k])>len(s)/2:return k
 D=d.values()
 for v in choice([g for g in D if len(g)==len(min(D,key=len))]):v.pop(0)
 return f(s)
from random import*

```

Try it online!

Takes input as a list of lists of voter prefernces (the header row is not included). The randomization in case of a tie is vexing!
> 0 votes

# Answer
# Perl 5 `-plF\|`, 155 bytes

```
%r?push@v,[@F]:map$r{$_}=1,@F}{while(@v/2>=$c{$\=pop@t}){map{shift@$_ while!$r{$$_[0]}}@v;%c=();map$c{$$_[0]}++,@v;$r{(@t=sort{$c{$a}-$c{$b}}keys%c)[0]}=0}

```

Try it online!
> 0 votes

# Answer
**Python 2, 200 bytes**

```
def f(s):
 d={}
 for v in s:
    k=v[0];d[k]=d.get(k,[])+[v]
    if len(d[k])>len(s)/2:return k
 D=d.values()
 x=[g for g in D if len(g)==len(min(D,key=len))]
 for v in x[id(x)%len(x)]:v.pop(0)
 return f(s)

```

Try it online!

Utilises the object ID of the array as a source of 'randomness'.
Based off Chas Brown's Answer \- I don't have enough rep to comment!
> 0 votes

---
Tags: code-golf
---


title: Skip like a rabbit!

text:
# Question
Title: Skip like a rabbit!
Given a list of non-negative integers in any reasonable format, iterate over it, skipping as many elements as every integer you step on says.

---

Here is a worked example:

```
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2] | []
 ^ First element, always include it
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2] | [0]
    ^ Skip 0 elements
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2] | [0, 1]
          ^ Skip 1 element
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2] | [0, 1, 2]
                   ^ Skip 2 elements
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2] | [0, 1, 2, 3]
Skip 3 elements; you're done

```

Another worked example, not so all-equal-deltas:

```
[4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2] | []
 ^ First element, always include it
[4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2] | [4]
                ^ Skip 4 elements
[4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2] | [4, 3]
                            ^ Skip 3 elements
[4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2] | [4, 3, 3]
                                        ^ Skip 3 elements
[4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2] | [4, 3, 3, 4]
Skip 4 elements; you're done

```

An out-of-bounds example:

```
[0, 2, 0, 2, 4, 1, 2] | []
^ First element, always include it
[0, 2, 0, 2, 4, 1, 2] | [0]
    ^ Skip 0 elements
[0, 2, 0, 2, 4, 1, 2] | [0, 2]
             ^ Skip 2 elements
[0, 2, 0, 2, 4, 1, 2] | [0, 2, 4]
Skip 4 elements; you're done (out of bounds)

```

---

# Rules

* You may not use any boring cheat among these ones, they make the challenge boring and uninteresting.
* You should only return/print the final result. STDERR output is ignored.
* You may not get the input as a string of digits in any base (e.g. "0102513162" for the first case).
* You must use left-to-right order for input.
* As in the worked examples, if you go out of bounds, execution terminates as if otherwise.
* You should use `0` for skipping 0 elements.
* Given the empty list (`[]`) as input, you should return `[]`.

---

# Test cases

```
[]                                                     => []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]                     => [0, 1, 3, 7]
[5, 1, 2, 3, 4, 5, 2, 1, 2, 1, 0, 0]                   => [5, 2, 1, 0]
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2]                         => [0, 1, 2, 3]
[4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2] => [4, 3, 3, 4]
[0, 2, 0, 2, 4, 1, 2]                                  => [0, 2, 4]

```

This is , so shortest answer wins!

# Answer
> 14 votes
# Python 2, 36 bytes

```
f=lambda x:x and x[:1]+f(x[x[0]+1:])

```

Try it online!

# Answer
> 13 votes
# Python 2, ~~49 44\*~~ 41 bytes

Crossed out 44 is still regular 44 :(

** -3 thanks to @ASCII-only*.

```
l=input()
while l:print l[0];l=l[l[0]+1:]

```

Try it online!

Prints the results separated by a newline, as the OP allowed in chat. I don't think it can get any shorter as a *non-recursive full program*.

---

# How does this work?

* `l=input()` \- Reads the list from the standard input.
* `while l:` \- Abuses the fact that empty lists are falsy in Python, loops until the list is empty.
* `print l[0];` \- Prints the first element of the list.
* `l=l[l[0]+1:]` \- "Skips like a rabbit" - Trims the first `l[0]+1` from the list.

### Let's take an example

Given the list `[5, 1, 2, 3, 4, 5, 2, 1, 2, 1, 0, 0]` as input, the code performs the following (according to the explanation above) - Prints the first item of the array: `5`, trim the first 6: `[2, 1, 2, 1, 0, 0]`. We then print `2` and trim the first 3: `[1,0,0]`. Likewise, we output `1`, crop the first 2, and we get `[0]`. Of course, `0` is printed and the program terminates.

# Answer
> 10 votes
# Haskell, ~~29 27~~ 26 bytes

```
j(x:y)=x:j(drop x y)
j x=x

```

Saved 1 byte thanks to Zgarb.

Try it online.

# Answer
> 9 votes
# JavaScript (ES6), ~~42~~ ~~39~~ 35 bytes

```
a=>a.map((n,i)=>a.splice(i+1,n))&&a

```

```
let f =
a=>a.map((n,i)=>a.splice(i+1,n))&&a

console.log(f([]))                                                     // => []
console.log(f([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))                     // => [0, 1, 3, 7]
console.log(f([5, 1, 2, 3, 4, 5, 2, 1, 2, 1, 0, 0]))                   // => [5, 2, 1, 0]
console.log(f([0, 1, 0, 2, 5, 1, 3, 1, 6, 2]))                         // => [0, 1, 2, 3]
console.log(f([4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2])) // => [4, 3, 3, 4]
console.log(f([0, 2, 0, 2, 4, 1, 2]))                                  // => [0, 2, 4]
```

### Old Solution 39 Bytes

```
a=>a.map(n=>i--||r.push(i=n),r=i=[])&&r

```

*-3 bytes thanks to @ThePirateBay*

# Answer
> 8 votes
# 05AB1E, ~~10~~ 9 bytes

```
[¬Dg>#=ƒ¦

```

Uses the **05AB1E** encoding. Try it online!

# Answer
> 8 votes
## Mathematica, ~~46~~ 44 bytes

```
SequenceCases[#,{x_,y___}/;Tr[1^{y}]<=x:>x]&

```

Alternatives:

```
SequenceCases[#,{x_,y___}/;x>=Length@!y:>x]&
SequenceCases[#,l:{x_,___}/;x>Tr[1^l]-2:>x]&

```

# Answer
> 7 votes
# C#, 68 bytes

```
a=>{for(int i=0;i<a.Count;i+=a[i]+1)System.Console.Write(a[i]+" ");}

```

Try it online!

Full/Formatted version:

```
namespace System
{
    class P
    {
        static void Main()
        {
            Action<Collections.Generic.List<int>> f = a =>
            {
                for (int i = 0; i < a.Count; i += a[i] + 1)
                    System.Console.Write(a[i] + " ");
            };

            f(new Collections.Generic.List<int>() { });Console.WriteLine();
            f(new Collections.Generic.List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });Console.WriteLine();
            f(new Collections.Generic.List<int>() { 5, 1, 2, 3, 4, 5, 2, 1, 2, 1, 0, 0 });Console.WriteLine();
            f(new Collections.Generic.List<int>() { 0, 1, 0, 2, 5, 1, 3, 1, 6, 2 });Console.WriteLine();
            f(new Collections.Generic.List<int>() { 4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2 });Console.WriteLine();
            f(new Collections.Generic.List<int>() { 0, 2, 0, 2, 4, 1, 2 });Console.WriteLine();

            Console.ReadLine();
        }
    }
}

```

---

Returning a list is longer at 107 bytes.

```
a=>{var l=new System.Collections.Generic.List<int>();for(int i=0;i<a.Count;i+=a[i]+1)l.Add(a[i]);return l;}

```

# Answer
> 6 votes
## Husk, ~~8~~ 6 bytes

```
←TU¡Γ↓

```

Try it online!

-2 bytes (and a completely new solution idea) thanks to Leo!

## Explanation

I'm using the list pattern match function `Γ`. It takes a function `f` and a list with head `x` and tail `xs`, and applies `f` to `x` and `xs`. If the list is empty, `Γ` returns a default value consistent with its type, in this case an empty list. We take `f` to be , which drops `x` elements from `xs`. This function is then iterated and the resulting elements are collected in a list.

```
←TU¡Γ↓  Implicit input, e.g. [0,2,0,2,4,1,2]
    Γ↓  Pattern match using drop
   ¡    iterated infinitely: [[0,2,0,2,4,1,2],[2,0,2,4,1,2],[4,1,2],[],[],[],...
  U     Cut at first repeated value: [[0,2,0,2,4,1,2],[2,0,2,4,1,2],[4,1,2],[]]
 T      Transpose: [[0,2,4],[2,0,1],[0,2,2],[2,4],[4,1],[1,2],[2]]
←       First element: [0,2,4]

```

# Answer
> 5 votes
# Python 2, ~~59~~ 55 bytes

```
l=input()
i=0
while l[i:]:i+=1;l[i:i+l[i-1]]=[]
print l

```

Try it online!

# Answer
> 5 votes
# Pyth, 22 Bytes

```
VQ aY.(Q0VeY .x.(Q0 ;Y

```

Removed a useless byte

# Answer
> 4 votes
# Python 2, ~~60~~ ~~42~~ 41 bytes

-18 bytes thanks to Luis Mendo
-1 byte thanks to Jonathan Frech

```
x=input()
i=0
while 1:print x[i];i-=~x[i]

```

Try it online!

# Answer
> 3 votes
## Retina, 36 bytes

Byte count assumes ISO 8859-1 encoding.

```
.+
$*
((1)*¶)(?<-2>1*¶)*
$1
%M`.
0$

```

Input and output are linefeed-separated with a trailing linefeed.

Try it online! (Uses commas instead of linefeeds to allow for convenient test suites.)

# Answer
> 3 votes
# Brain-Flak, 64 bytes

```
([]){{}(({})<>)<>{({}[()]<{}>)}{}([])}{}<>([]){{}({}<>)<>([])}<>

```

Try it online!

```
([]){{}                          ([])}{}                         # Until the stack is empty
       (({})<>)<>                                                # Copy TOS to off stack
                 {({}[()]<{}>)}{}                                # Pop TOS times
                                        <>([]){{}({}<>)<>([])}<> # Reverse off stack

```

# Answer
> 2 votes
# Mathematica, ~~64~~ 50 bytes

```
±x_List:=Prepend[±Drop[x,1+#&@@x],#&@@x]
±_=±{}={}

```

# Answer
> 2 votes
# Java (OpenJDK 8), 53 bytes

Thanks to @PunPun1000 and @TheLethalCoder

```
a->{for(int n=0;;n+=1+a[n])System.out.println(a[n]);}

```

Try it online!

# Answer
> 2 votes
# R, 58 bytes

```
f=function(x,p=1){cat(z<-x[p]);if(p+z<sum(x|1))f(x,p+z+1)}

```

Recursive function. Takes a vector `x` as argument and intiates a pointer `p`. This prints the corresponding entry of `x`, checks if `p+x[p]` would go out of bounds, and if not, calls the function for the new pointer.

```
f=function(x,p=1,s=x[1])`if`((z<-x[p]+p+1)>sum(x|1),s,f(x,z,c(s,x[z])))

```

This is a comparable solution that returns a proper vector instead of printing the digits.

# Answer
> 2 votes
# C# (.NET Core), 68 bytes

```
n=>{var t="";for(int i=0;i<n.Length;i+=n[i]+1)t+=n[i]+" ";return t;}

```

Try it online!

Takes input as an array of integers, returns a string containing the non-skipped values.

# Answer
> 2 votes
## Alice, 15 bytes

```
/$.. \h&
\I@nO/

```

Try it online!

Input and output a linefeed-separated lists of decimal integers.

### Explanation

```
/   Switch to Ordinal mode.
I   Read a line.
.   Duplicate it.
n   Logical NOT (gives truthy if we're at EOF).
/   Switch to Cardinal.
    The IP wraps around to the left.
\   Switch to Ordinal.
$@  Terminate the program if we're at EOF.
.   Duplicate the input line again.
O   Print it.
\   Switch to Cardinal.
h   Increment the value.
&   Store the result in the iterator queue.
    The program wraps around to the beginning.

```

Storing an integer **n** in the iterator queue causes the next command to be executed **n** times. Mirrors like `/` are not commands, so the next command will be `I`. Therefore if we just read and printed a value **x**, we will read **x+1** values on the next iteration, with the last of them ending up on top of the stack. This skips the required number list elements.

# Answer
> 2 votes
## *Mathematica*, 37 (30?)

Further golfing of user202729's fine method.

```
±{a_,x___}={a}~Join~±{x}~Drop~a
±_={}

```

The rules don't seem to explicitly specify the output format, so maybe:

```
±{a_,x___}=a.±{x}~Drop~a
±_={}

```

Output for the second function looks like: `0.2.4.{}` — notably `{}` is still returned for an empty set, conforming to the final rule.

# Answer
> 2 votes
# Common Lisp, 51 bytes

```
(do((x(read)(nthcdr(1+(print(car x)))x)))((not x)))

```

Try it online!

# Answer
> 2 votes
# Brain-Flak, ~~64~~ 60 bytes

*4 bytes save based on an idea from 0 '*

```
([]){{}(({})<>())<>{({}[()]<{}>)}{}([])}{}<>{({}[()]<>)<>}<>

```

Try it online!

## Annotated

```
([]){{}            #{Until the stack is empty}
  (({})<>())<>     #{Put n+1 to the offstack}
  {({}[()]<{}>)}{} #{Remove n items from the top}
([])}{}            #{End until}
<>                 #{Swap stacks}
{({}[()]<>)<>}<>   #{Move everything back onto the left stack decrementing by 1}

```

# Answer
> 1 votes
## Python 2.4, 85 bytes

No chance to win in python with it, but I love oneliners and this one might be interesting to others.
Turns out, there is a fancy magic trick to access building list inside comprehension, but it works only in 2.4 and with some edits in \<= 2.3
`locals()['_[1]']` it is. Python creates secret name `_[1]` for list, while it is created and store it in `locals`. Also names `_[2]`, `_[3]`... are used for nested lists.

```
lambda n:[j for i,j in enumerate(n)if i==len(locals()['_[1]'])+sum(locals()['_[1]'])]

```

So it counts number of already added elements plus their sum. Result is the index of next desired element.
I think, that there should be a way to avoid enumerate. Like accessing input array directly by index: `[ n[len(locals()['_[1]'])+sum(locals()['_[1]'])] for ... ]`. But I can't figure out a compact way to protect it from index-out-of-range (while keeping it oneliner)

# Answer
> 1 votes
# Ruby, ~~36 33~~ 31

```
f=->l{a,*l=l;a&&f[l.drop(p a)]}

```

Try it online.

# Answer
> 1 votes
# Swift, 63 bytes

```
func a(d:[Int]){var i=0;while i<d.count{print(d[i]);i+=d[i]+1}}

```

This is my first entry, ever, so I'm not 100% sure on the rules, but hopefully this answer suffices. I'm a little unsure of rules on how to get the input into a system. I have a shorter answer if I was allowed to assume a function somewhere that can return the input.

# Answer
> 1 votes
# Perl 5, ~~36~~ 30 + 1 (-a) = 31 bytes

```
$i+=$F[$i]+say$F[$i]while$i<@F

```

Try it online!

Takes its input as a space separated list of numbers.

# Answer
> 1 votes
# Perl 6, 31 bytes

```
{(@_,{.[1+.[0]..*]}...^0)[*;0]}

```

Test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢@_｣
  (
    # generate a sequence

    @_,

    {
      .[ # index into previous value in the sequence
        1 + .[0]  # start by skipping one plus the first element
                  # of the previous value in the sequence
        ..  *     # use that to create a Range with no end
      ]
    }

    ...^  # keep doing that until: (and throw away last value)
    0     # it generates an empty list

  )[ *; 0 ]  # from every value in the sequence, get the first element
}

```

To help understand how the code works, without `[*;0]` this would generate a sequence like the following:

```
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2],
   (1, 0, 2, 5, 1, 3, 1, 6, 2),
         (2, 5, 1, 3, 1, 6, 2),
                  (3, 1, 6, 2)

```

# Answer
> 1 votes
# C++ (gcc), 172 bytes

(for 144 bytes see @ceilingcat comment)

```
#include<iostream>
int main(){std::istream& i=std::cin;char c;int a,b;while(i>>c&&i>>a){std::cout<<c<<(c/91?"":" ")<<a;while(a--&&i>>c&&i>>b);}std::cout<<c<<(c/93?"":"]");}

```

Try it online

The awful `(c/91?"":" ")` is for correct spacing in output. Without it (-15 bytes) output is in form: `[0,2,4]`, when I change it to simple `" "` (-9 bytes) output is like `[ 0, 2, 4]` (additional space at the beginning).

`<<(c/93?"":"]")` on the end is only to handle `[]` empty input corner case

Prints no trailing endline.

# Answer
> 1 votes
# Jelly, 8 bytes

```
ḢṄ‘ṫ@µL¿

```

A full program printing the results each followed by a newline (empty list produces no output).

**Try it online!**

### How?

```
ḢṄ‘ṫ@µL¿ - Main link: list of non-negative integers  e.g. [2,5,4,0,1,2,0]
       ¿ - while:           Iteration:  1                  2             3          4        5
      L  -   length (0 is falsey)       7                  4             3          1        0
     µ   - ...do:                                                                            stop
Ḣ        -   head (pop & modify)        2 ([5,4,0,1,2,0])  0 ([1,2,0])   1 ([2,0])  0 ([0])
 Ṅ       -   print it (and yield it)   "2\n"              "0\n"         "1\n"      "0\n"
  ‘      -   increment                  3                  1             2          1
   ṫ@    -   tail from index            [0,1,2,0]          [1,2,0]      [0]         []
         -
         -                       i.e. a resulting in the printing of: '''2
                                                                         0
                                                                         1
                                                                         0
                                                                         '''

```

# Answer
> 1 votes
# Python 3, 35 bytes

```
f=lambda h=0,*t:t and[h,*f(*t[h:])]

```

Try it online!

Run it with `f(*l)` where `l` is your input. Arguably stretching the rules for input, but I just love advanced unpacking.

# Answer
> 1 votes
# APL (Dyalog Unicode), 20 bytesSBCS

```
{⍵≡⍬:⍬⋄(⊃,∘∇1↓⊃↓⊢)⍵}

```

Try it online!

# Answer
> 1 votes
# PowerShell, 25 bytes

```
$args|?{!$s--}|%{($s=$_)}

```

Try it online!

# Answer
> 0 votes
# Mathematica, 65 bytes

```
(s=#;t=1;w={};While[t<=Length@s,AppendTo[w,k=s[[t]]];t=t+k+1];w)&

```

Try it online!

# Answer
> 0 votes
# Clojure, 67 bytes

```
#(nth(reduce(fn[[z k]b](if(= z 0)[b(conj k b)][(- z 1)k]))[0[]]%)1)

```

Starts with the initial parameters `[0 []]`, where `0` is the counter and `[]` is the result. If the first element in this list is `0` appends item `n` from the argument to the result and passes further this list `[n [... n]]` otherwise decrements the first element. (this explanation feels horrible to me)

See it online

# Answer
> 0 votes
## Batch, 69 bytes

```
:l
@if not "%1"=="" echo %1&(for /l %%i in (0,1,%1)do @shift)&goto l

```

(I need the `()`s around the `for` otherwise the `goto` happens inside the loop.)

# Answer
> 0 votes
# C (gcc), 100 96 93 90 65 61 58 bytes

```
s;main(d){while(scanf("%d",&d)>0)s--||printf("%d\n",s=d);}

```

Try it online!

* recursive `main()` saves a few bytes, yay!
* indexing into string saves another 3 bytes
* relaxing the output format saves a **whole lot** of bytes (25 to be exact), see here the shortest version with nice list-style output (90 bytes):

```
s;d;main(p){scanf("%*c %d",&d)>0?s--||printf(p?"[%d":", %d",s=d),main(0):printf("[]"+!p);}

```
* a different input format (1 number per line) saves *another* 4 bytes
* Now it's shorter *without* recursion

# Answer
> 0 votes
# Perl 6, 33 bytes

```
my&f={$_&&(.[0],|f .[.[0]+1..*])}

```

Try it online!

# Answer
> 0 votes
# Cubix, 24 bytes

```
U.;@I)!/(O?vL!(.;I<.oWSL

```

Try it online!

Takes input as a comma- (or whitespace-) separated list with a `-1` at the end to signify end of input.

I expect there's some golfing to do here.

Expands to the following cube:

```
    U .
    ; @
I ) ! / ( O ? v
L ! ( . ; I < .
    o W
    S L

```

Algorithm is in two parts:

* `I)` : read in an input, increment it.
* `!/` : If zero (i.e., input is -1), turn left to `@` and end program, otherwise proceed
* `(O` : decrement and output as a number
* `?` : if zero, go straight, if positive, turn right.

Positive case:

* `<I` : go right and read in input
* `;(` : pop TOS and decrement TOS
* `!L` : skip `L` (turn left) if TOS is nonzero
* wrap around to `<I` again
* otherwise we hit `SLWo(!;U` which is the same as the zero case.

Zero case:

* `vS` : go down, push `32` (space character)
* `o(` : output as a character, decrement
* `!;` : (no ops)
* `U` : re-enter main loop, `I)!/` etc.

# Answer
> 0 votes
# Jelly, 7 bytes

```
ḊḢṄ$¡¹¿

```

Try it online!

Since nobody has discovered this yet (I challenged Jonathan Allan a long time ago), I am posting it.

# Jelly, 12 bytes

```
Ḋ1ị$‘$¡ÐĿṖḢ€

```

Try it online!

I had 18 bytes back then (can't remember the exact code), but now I managed to make a list-returning version in 12 bytes.

# Answer
> 0 votes
# PHP, 74 bytes

```
function s($l){$k=0;while(isset($l[$k]))$k+=($r[]=$l[$k])+1;return$r?:[];}

```

Try it online!

# Answer
> 0 votes
# PowerShell, ~~57~~ 50 bytes

-7 bytes thanks to mazzy

```
param($l)for(;$i-lt$l.count){($z=$l[$i++]);$i+=$z}

```

Try it online!

Simple for-loop approach that does alright.

# Answer
> 0 votes
# Japt, 5 bytes

Modifies the input array in place.

```
£jYÄX

```

Try it \- Footer outputs the original array

# Answer
> 0 votes
# Javascript 2019, ~~43~~ 42 chars

```
a=>a.flatMap(x=>i^q++?[]:(i+=x+1,x),i=q=0)

```

Test:

```
f=a=>a.flatMap(x=>i^q++?[]:(i+=x+1,x),i=q=0)

console.log(
`[]                                                    => []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]                     => [0, 1, 3, 7]
[5, 1, 2, 3, 4, 5, 2, 1, 2, 1, 0, 0]                   => [5, 2, 1, 0]
[0, 1, 0, 2, 5, 1, 3, 1, 6, 2]                         => [0, 1, 2, 3]
[4, 5, 1, 3, 8, 3, 0, 1, 1, 3, 1, 2, 7, 4, 0, 0, 1, 2] => [4, 3, 3, 4]
[0, 2, 0, 2, 4, 1, 2]                                  => [0, 2, 4]`
.split`
`.map(s=>s.split`=>`)
.map(([s,key])=>f(eval(s))==""+eval(key))
)
```

# Answer
> 0 votes
# Runic Enchantments, 25 bytes

```
>Ri:$' $\
~/i~1-!;R:0)2*?

```

Try it online!

But input and output are space-separated integer lists. There is a trailing space because the logic to check to see if any input was actually read is a pain (and about 7 bytes) and not strictly needed for processing of this sort.

# Answer
> 0 votes
# Stax, 5 bytes

```
√⌡╜9{

```

Run and debug it

# Answer
> 0 votes
# PHP, 66 bytes

```
function($a){for(;$x<count($a);$x+=$o[]=$a[$x++|0]);return$o?:[];}

```

Try it online!

**Output:**

```
[]                                       => []
[0,1,2,3,4,5,6,7,8,9,10]                 => [0,1,3,7]
[5,1,2,3,4,5,2,1,2,1,0,0]                => [5,2,1,0]
[0,1,0,2,5,1,3,1,6,2]                    => [0,1,2,3]
[4,5,1,3,8,3,0,1,1,3,1,2,7,4,0,0,1,2]    => [4,3,3,4]
[0,2,0,2,4,1,2]                          => [0,2,4]

```

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


title: Tetris Tangrams

text:
# Question
Title: Tetris Tangrams
## Introduction

Tangrams are a classic puzzle involving arranging/fitting blocks into various shapes. From the Chinese 七巧板 - literally meaning "seven boards of skill". Let's take this idea and use the seven Tetrominos pieces to fill a grid.

## Challenge

Write a function or program that takes an array of grid coordinates as input, and outputs a completed 10 by 20 grid filled with Tetris pieces except in the specified coordinates.

Optimize your score by attempting to keep the distribution of pieces uniform.

## Criteria

Use this pastebin of coordinates to accomplish your task. There are five sets of coordinates. Feel free to modify the format in which the coordinates are written, but not the values.

Data set #2 cannot be solved - in this case, simply output the grid with input cells filled in (i.e., `X`'s where the holes are).

## Input

Grid coordinates represent 'holes' in the grid. These are cells which cannot contain any part of a Tetromino.

**Grid coordinates:**

```
(0,0), (1,0), (2,0), ... (9,0)
(0,1), (1,1), (2,1), ... (9,1)
.
.
.
(0,19), (1,19), (2,19), ... (9,19)

```
* Use your programming language's array style of choice to input the coordinates.
* Represent holes in the grid with an `X` or other printable ASCII.

## Output

Using a standard Tetris grid size of **10 cells wide by 20 cells tall**, print a solution grid if and only if the grid can be filled completely and perfectly using Tetromino pieces.

Pieces constructed with letters `I`, `O`, `L`, `J`, `T`, `Z`, `S` as follows:

```
I
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

```

---

## Example

Output solution example with no input coordinates:

```
ZZIIIILLLI
JZZTTTLLLI
JJJSTLOOLI
SZZSSLOOLI
SSZZSLLJJI
TSOOSLLJII
TTOOSSLJII
TZOOSSLZII
ZZOOSSZZII
ZJJJJSZLLI
TTTJJOOILI
ITZJJOOILI
IZZTTTLIII
IZOOTZLIII
IJOOZZLLII
LJJJZSSTII
LLLTSSTTTI
LLLTTSSZJI
OOLTSSZZJI
OOIIIIZJJI

```

With distribution as follows:

```
I
I          L      J
I    OO    L      J     T     ZZ      SS
I    OO    LL    JJ    TTT     ZZ    SS

11   6     8     6      6     7      6

```

---

## Notes

Coordinates represent a single `X` and `Y` position on the grid. The grid is 0 based, meaning coordinate `(0,0)` should either be the top left or the bottom left cell, author's choice.

Bricks can:

* be selected at author's discretion.
* be rotated as author sees fit.
* be placed on the grid anywhere at author's discretion (aka: no Tetris gravity)

Bricks cannot:

* be placed outside the bounds of the grid.
* overlap an existing brick or hole in the grid.
* be a non-standard Tetris tetromino piece.

---

## Scoring

Your score is in the format:

**( 1000 - \[bytes in code\] ) * ( M / 10 + 1 )**

Where M is a multiplier for the distribution of pieces used in your solution sets.

Highest score by the Ides of March wins.

To calculate M, add the lowest individual tetromino distribution value for each set and then take the average rounded down to calculate M.

For example:

```
Set 1: 5
Set 2: 4
Set 3: 5
Set 4: 6
Set 5: 3

```

6 + 4 + 5 + 4 + 4 = 21 / 5 = 4.6

So you would use `4` as your **M** value.

Note: If a set has no solution, do not factor that set into calculating M, since it would have no tetromino distribution.

# Answer
# Python 3, 819 bytes, M=0, Score=*181*

This is a brute force DFS program. It builds a numpy array, and inserts all the inputted holes. It then takes the leftmost unfilled tile on the highest row that has one, and places a tetromino. Recursively, we now do it again - when we can't either we found a solution, or we backtrack and try another piece at the first opportunity.

This has an **M** of 0, since it tries to use pieces in a determined order, and almost always finds a solution without the last one in the list. I tried using a randomly ordered list each cycle to make a more even distribution, but I only got an **M** of 2, which wasn't worth the bytes required to import *random.shuffle*.

I can't comment the below code, since in my golfing I've long forgotten what much of it does. The general idea:

* Import numpy and itertools product, with 1-letter names
* Rename some builtins to be 1-letter functions, and define a lambda to save bytes
* Build the array of possible tetrominos as numpy nd-arrays, all rotations included
* In the recursive function:
    + Get the position of the unfilled tile desired, and cycle through the pieces list
    + For each piece, cycle through translations of it (moving it up and down)
    + If something doesn't work (piece goes off the board, hits another piece, hits a hole, etc.), try the next translation or the next entire piece
    + If it works, great. Try it, then recursively call the function.
    + If that path didn't work, it will return 'a', so we just try again. If it did work, it returns the board, and we pass it up the line.
* Finally, the program. We build the 10x20 board as a numpy array of 1's.
* The input is of the form *(x1, y1);(x2,y2);...* We put a 9 for each hole in it, then get the result of running the function on it.
* The print statement then displays either the successful result or the empty, original board line by line, substituting the appropriate letters or symbols for the numbers.

```
import numpy as n
from itertools import product as e
m,s=range,len
p=[n.rot90(a,k)for a,r in[([[2,2]]*2,1),([[3]*3,[1,3,1]],4),([[0]*4],2),([[1,1,6],[6]*3],4),([[7,1,1],[7]*3],4),([[4,4,1],[1,4,4]],2),([[1,5,5],[5,5,1]],2)]for k in m(r)]
o=lambda a:e(m(s(a)),m(s(a[0])))
def t(l,d=0):
	g=list(zip(*n.where(l==1)))[0]
	for a in p:
		for u,v in o(a):
			w,x=l.copy(),0
			for r,c in o(a):
				if a[r,c]!=1:
					i,j=g[0]+r-u,g[1]+c-v
					if any([i<0,i>19,j<0,j>9])or l[i,j]!=1:
						x=1
						break
					w[i,j]=a[r,c]
			if x==0:
				if len(w[w==1]):
					f=t(w,d+1)
					if type(f)==str:continue
					return f
				return w
	return'a'
b=n.ones((20,10))
b[list(zip(*[eval(k)[::-1]for k in input().split(';')]))]=9
a=t(b)
for r in(a,b)[type(a)==str]:
	print(''.join(map(dict(zip([0,2,3,4,5,6,7,9,1],'IOTZSLJX-')).get,r)))

```

Try it online!

Sample test:

```
In: (1,1);(8,1);(4,4);(5,8);(4,11);(5,15);(1,18);(8,18)
Out:
IIIIOOOOLL
TXOOOOOOXL
TTOOOOOOTL
TOOIOOOOTT
TOOIXOOTTI
TTTITOOTTI
TTTITTTTII
OOTTTTTTII
OOTTTXOOII
TTTTOOOOII
TTTTOOOOII
TTTTXTOOII
ITTTTTTTII
ITTTTTTTII
IITTTLLTTI
IITOOXLTTI
IITOOTLTTI
IITTLTTTTI
IXTLLTJTXI
ILLLLLJJJI

```
> 2 votes

---
Tags: code-challenge, optimization, tetris, packing
---


title: Make Gimbap cutter

text:
# Question
Title: Make Gimbap cutter
Gimbap(김밥) is Korean food, somewhat looks like sushi roll.

Here is Korean emoticon represent Gimbap : `@))))))))))`

Your quest is make ASCII Gimbap cutter.

# Rule

Input is string made with only `@` and `)`.

Output *cuts* every valid Gimbap with `)`, and then add  `@` between them. So for example `@))` to `@) @)`.

*Valid Gimbap* starts with `@` and followed by any amount of `)`.

If there is no valid Gimbap, output is blank.

# Input and output

```
Input | Output
@))))) | @) @) @) @) @)
@))))))) | @) @) @) @) @) @) @)
@))@))) | @) @) @) @) @)
@) | @)
)) |
@ |
@@)@@@))) | @) @) @) @)
@)@)@)) | @) @) @) @)
@@@)) | @) @)
))@) | @)

```

# Winning condition

This is , so shortest code wins.

from sandbox

# Answer
> 10 votes
# Haskell, 32 bytes

```
f(')':s)=f s
f s=do ')'<-s;"@) "

```

Try it online!

Recursion beats using `span` for removing the initial `(`'s.

**Haskell, 33 bytes**

```
f s=do ')'<-snd$span(<'@')s;"@) "

```

Try it online!

# Answer
> 7 votes
# JavaScript, ~~42~~ 41 bytes

```
s=>s.split(/(?<=@.*)\)/).fill``.join`@) `

```

Try It Online!

# Answer
> 5 votes
# Canvas, ~~10~~ 9 bytes

```
@ｓｊ∑Ｌ@) ×

```

Try it here!

# Answer
> 5 votes
# C (gcc), 53 bytes

```
i;f(char*_){for(i=1;*_;!i&*_++&&printf("@) "))i&=*_;}

```

Try it online!

```
i;f(char*_){for(    *_;                      )      }   //loop over the string:
                i=1;   !i&                    i&=*_;    //skip leading `)`s
                       !i&*_++&&printf("@) ")           //and print "@) "for each `)` thereafter

```

# Answer
> 5 votes
# JavaScript (Node.js), ~~48~~ 47 bytes

```
x=>"@) ".repeat(x.split(/(?<=@.*)\)/).length-1)

```

Try it online!

# JavaScript (Node.js), ~~53~~ 49 bytes

```
x=>[...x].map(y=>y<"0"?m+=s&&"@) ":s=1,s=m="")&&m

```

Try it online!

# JavaScript (Node.js), 60 bytes

```
x=>x.replace(/(@?)(\)*)/g,(_,a,b)=>a&&b.replace(/./g,"@) "))

```

Try it online!

# Answer
> 4 votes
# Retina 0.8.2, 14 bytes

```
^\)+|@

\)
@)

```

Try it online! Link includes test cases. Explanation:

```
^\)+|@

```

Delete leading `)`s and all `@`s.

```
\)
@)

```

Replace all `)`s with `@)`s. (Note: trailing space.)

# Answer
> 3 votes
# Python 2, 39 bytes

```
lambda s:'@) '*s.lstrip(')').count(')')

```

Try it online!

# Answer
> 3 votes
# Jelly, 8 bytes

```
ṣṀḊẎ”@pK

```

Try it online!

-1 thanks to Jonathan Allan.

# Answer
> 2 votes
# Perl 5 `-p`, 26 bytes

```
$_=s/^.*?@//&&'@) 'x y/)//

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 12 bytes

```
')Û'@KS'@ìðý

```

Try it online!

**Explanation**

```
')Û            # trim leading ")"
   '@K         # remove all "@"
      S        # split to list of characters
       '@ì     # prepend "@" to each
          ðý   # join on spaces

```

# Answer
> 2 votes
## Batch, 58 bytes

```
@set s=%1@
@set s=%s:*@=(%
@set s=%s:@=%
@echo%s:)=@) %

```

Takes input as a command-line parameter. Explanation:

```
@set s=%1@

```

Suffix an `@` in case the input doesn't contain any.

```
@set s=%s:*@=(%

```

Delete up to the first `@`, replacing it with a `(` to ensure that the string is not empty (because `%:%` doesn't work on empty strings). The `(` also makes the `echo` work if the rest of the string is empty.

```
@set s=%s:@=%

```

Delete any remaining `@`s.

```
@echo%s:)=@) %

```

Expand any remaining `)`s.

# Answer
> 2 votes
# Japt v2.0a0 `-S`, 15 bytes

```
r/^\)+|@/ ¬mi'@

```

Try it

```
r/^\)+|@/ ¬mi'@     :Implicit input of string
r                   :Remove
 /^\)+|@/           :  "@"s and leading ")"s
          ¬         :Split
           m        :Map
            i'@     :  Prepend "@"
                    :Implicit output, joined with spaces

```

## Alternative

```
e/^\)/ è\) Æ"@)

```

Try it

```
e/^\)/ è\) Æ"@)     :Implicit input of string
e                   :Recursively remove
 /^\)/              :  Leading ")"
       è\)          :Count remaining ")"s
           Æ        :Map the range [0,Count)
            "@)     :  Literal string
                    :Implicit output, joined with spaces

```

# Answer
> 2 votes
# 05AB1E (legacy), 10 bytes

```
Z¡¦JS'@ìðý

```

Try it online!

This bug forces me to use the legacy version. This is the code for the current version of 05AB1E (11 bytes):

```
'@¡¦JS'@ìðý

```

Try it online!

Port of my Jelly answer.

# Answer
> 2 votes
# brainfuck, 49 bytes

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

```

Try it online!

# Answer
> 1 votes
# Japt v2.0a0 `-P`, 15 bytes

```
f/@\)+/ ËÅç"@)

```

Saved 2 bytes thanks to @Shaggy.

Try it

# Answer
> 1 votes
# Jelly, 12 bytes

```
œl”)ḟ”@⁾@ jⱮ

```

Try it online!

# Answer
> 1 votes
# Perl 6, 34 bytes

```
{~map {'@)'xx.chars-1},m:g/\@\)+/}

```

Try it online!

# Answer
> 1 votes
# Ruby `-p`, 28 bytes

```
$_= ~/@/&&'@) '*$'.count(?))

```

Try it online!

**Explanation**

```
                                # -p gets a line of STDIN
$_=                             # Set output to
    ~/@/                        # Find first '@' in input
                                # nil (falsey) if not found
        &&                      # If found, set output to
          '@) '                 # Sliced gimbap
               *                # Repeat
                $'              # In the string after the first '@',
                  .count(?))    # ... count the number of ')'
                                # -p outputs the contents of $_
                                # nil outputs as a blank string

```

# Answer
> 1 votes
# Java 10, 49 bytes

```
s->s.replaceAll("^\\)+|@+","").replace(")","@) ")

```

Try it online.

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~91~~ ~~90~~ ~~85~~ ~~71~~ ~~70~~ ~~59~~ 57 bytes

```
StringReplace@{(StartOfString~~")"..)|"@"->"",")"->"@) "}

```

Try it online!

# Answer
> 1 votes
# sed, 30 bytes

```
s/)\?@\()\?\)/\1/g; s/)/@) /gp

```

Try it online!

# Answer
> 1 votes
# Pyth, 20 bytes

```
*?}\@z/>zxz\@\)0"@)

```

Try it online! Note that there is a trailing space at the end of the program. This one is (or rather, started out as) a rather direct translation of the Python 2 answer (though the lstrip part was surprisingly difficult).

Explanation:

```
*            # repeat string
  ?          # repeat count: ternary
    }\@z     # condition: check whether input contains @
    /        # if condition is true: count occurrences of one string in another
      >      # array slice: all elements of array (or string) from a specific index and upwards
        z    # the thing to slice (input)
        xz\@ # the index first occurrence of \@ in z
      \)     # string to count occurrences of (\x is shorthand for "x")
    0        # value when ternary condition is false
  "@) "      # the string to be repeated (automatically terminated by end-of-line)

```

# Answer
> 1 votes
# krrp, 63 bytes

```
^":\L,^*':?#?E'E!-@1#!r'?=#!f'$64.-?*L$64.L$41.L$32.-@0#!r'.0".

```

Try it online!

---

# Explanation

```
^":                   ~ take the string as a parameter named `"`
 \L                   ~ import the list module
 ,^*':                ~ apply a binary function
  ?#?E'               ~  if the string is empty,
   E                  ~   return the empty string; else
   !-@1#!r'           ~   define `-` as the cut Gimbap
   ?=#!f'$64.         ~    if an at sign is seen,
    -                 ~    return the cut Gimbap; else
    ?*                ~    if an at sign has been seen,
     L$64.L$41.L$32.- ~     return a Gimbap piece together
                      ~     with freshly cut Gimbap; else
     @0#!r'           ~     proceed to cut
 .0".                 ~ to zero and the above taken string

```

Try it online!

# Answer
> 1 votes
# PowerShell, 42 bytes

```
''+($args|sls '(?<=@.*)\)'-a|% m*|%{'@)'})

```

Try it online!

Unrolled:

```
$arrayOfCuttedGimbaps = $args|select-string '(?<=@.*)\)' -AllMatches|% Matches|%{'@)'}
''+($arrayOfCuttedGimbaps)    # toString and output

```

---
Tags: code-golf, ascii-art
---