# Question
Title: Find elements in an array computing a given function value
# Problem Description

Given:

* a function \\$f(a, b, c, d, e) = \frac{a \times b}c + \frac de\\$
* an array \\$x = \[x\_1, x\_2, x\_3, x\_4, ..., x\_n\]\\$ of non-distinct integers
* a target value \\$k\\$

What is the most efficient way, in terms of worst-case \\$n\\$, to find 5 distinct indices \\$x\_a, x\_b, x\_c, x\_d, x\_e\\$ from \\$x\\$ such that \\$f(x\[x\_a\], x\[x\_b\], x\[x\_c\], x\[x\_d\], x\[x\_e\]) = k\\$?

# Example solutions

## Example 1 (single solution):

\\$x = \[0, 1, 2, 3, 4, 5, 6, 7, 8, 9\], k = 5\\$

## Solution 1:

\\$\[1, 4, 2, 9, 3\]\\$ as \\$f(x\[1\], x\[4\], x\[2\], x\[9\], x\[3\])\\$ evaluates to \\$5\\$.

## Example 2 (multiple solutions):

\\$x = \[0, -1, 1, -1, 0, -1, 0, 1\], k = 0\\$

## Solution 2 (of many solutions):

\\$\[1, 2, 3, 5, 7\]\\$ OR \\$\[0, 1, 2, 4, 7\]\\$

## Example 3 (no solution):

\\$x = \[0, -1, 1, -1, 0, -1, 0, 1\], k = 8\\$

## Solution 3:

\\$-1\\$ (no solution)

## Example 4 (intermediary floats):

\\$x = \[2, 3, 5, 4, 5, 1\], k = 2\\$

## Solution 4:

\\$\[2, 3, 5, 4, 5\]\\$

# Answer
# Python3, O(n^3 log n)

```
from math import gcd
from functools import reduce

def lcm(x,y):
    return x//gcd(x,y)*y

def label(l):
    res=[(v,i) for i,v in enumerate(l)]
    res.sort()
    return res

def sortcombine(l):
    l.sort()
    res=[]
    oldval=None
    for val,how in l:
        if val==oldval:
            res[-1][1].append(how)
        else:
            oldval=val
            res.append((val,[how]))
    return res

def getabc(L,xl):
    N=len(xl)
    res=[]
    lasta=None
    for ai in range(N):
        a,al=xl[ai]
        if a==lasta:
            continue
        lasta=a
        lastb=None
        for bi in range(ai+1,N):
            b,bl=xl[bi]
            if b==lastb:
                continue
            lastb=b
            lastc=None
            for c,cl in xl:
                if c in [0,lastc] or cl in [al,bl]:
                    continue
                lastc=c
                res.append((L//c*a*b,(al,bl,cl)))
    return sortcombine(res)

def getde(L,xl):
    res=[]
    xl.reverse()
    lastd=None
    for d,dl in xl:
        if lastd==d:
            continue
        lastd=d
        laste=None
        for e,el in xl:
            if e in [0,laste] or el==dl:
                continue
            laste=e
            res.append((L//e*d,(dl,el)))
    return sortcombine(res)

def solve(l,k):
    xl=label(l)
    L=reduce(lcm,[v for v in l if v!=0],1)
    k*=L
    abc=getabc(L,xl)
    de=getde(L,xl)
    i=0
    j=len(de)-1
    while i<len(abc) and j>=0:
        v1,ls1=abc[i]
        v2,ls2=de[j]
        s=v1+v2
        if s==k:
            for l1 in ls1:
                s=set(l1)
                for l2 in ls2:
                    if s.isdisjoint(l2):
                        return list(l1+l2)
            i+=1
            j-=1
        elif s<k:
            i+=1
        else:
            j-=1
    return None

```

Try it online!

Multiply the equation by the LCM of the x values to avoid floating point or fractions. Find all possible values of `ab/c` (using `ab=ba` but that's only for a factor of 1/2) and `d/e`, sort them and try to add them to the wanted result. The sorting means we don't have to try all combinations.

There are O(n^3) possible values for `ab/c`, sorting them gives the `log`. The other steps are faster than that.

The `while` loop may be repeated O(n^3) times, but the case `s==k` can only occur O(n^2) times. If we don't find a solution and stop in this case, then the sizes of `ls1` and `ls2` (number of ways to obtain the corresponding value) must be in O(n) resp. O(1) (except in the case when the value is 0, but luckily that doesn't happen O(n) times).
> 1 votes

---
Tags: fastest-algorithm
---


title: Counting groups of a given size

text:
# Question
Title: Counting groups of a given size
### Groups

In abstract algebra, a *group* is a tuple \\$(G,\ast)\\$, where \\$G\\$ is a set and \\$\ast\\$ is a function \\$G\times G\rightarrow G\\$ such that the following holds:

* For all \\$x, y, z\\$ in \\$G\\$, \\$(x\ast y)\ast z=x\ast(y\ast z)\\$.
* There exists an element \\$e\\$ in \\$G\\$ such that for all \\$x\\$ in \\$G\\$, \\$x\ast e=x\\$.
* For each \\$x\\$ in \\$G\\$, there exists an element \\$y\\$ in \\$G\\$ such that \\$x\ast y=e\\$.

The *order* of a group \\$(G,\ast)\\$ is defined as the number of elements of \\$G\\$.

For each strictly positive integer \\$n\\$, there exists at least one group of order \\$n\\$. For example, \\$(C\_n,+\_n)\\$ is such a group, where \\$C\_n=\\{0,...,n-1\\}\\$ and \\$x+\_ny=(x+y)\mod n\\$.

### Isomorphic groups

Let \\$G:=\\{1,2\\}\\$ and define \\$\ast\\$ by \\$x\ast y=(x\times y)\mod3\\$. Then \\$1\ast1=1=2\ast2\\$ and \\$1\ast2=2=2\ast1\\$.

Likewise, \\$0+\_20=0=1+\_21\\$ and \\$0+\_21=1=1+\_20\\$.

Although the elements and operations of the groups \\$(G,\ast)\\$ and \\$(C\_2,+\_2)\\$ have different names, the groups share the same structure.

Two groups \\$(G\_1,\ast\_1)\\$ and \\$(G\_2,\ast\_2)\\$ are said to be *isomorphic* if there exists a bijection \\$\phi:G\_1\rightarrow G\_2\\$ such that \\$\phi(x\ast\_1y)=\phi(x)\ast\_2\phi(y)\\$ for all \\$x,y\\$ in \\$G\_1\\$.

Not all groups of the same order are isomorphic. For example, the Klein group is a group of order 4 that is not isomorphic to \\$(C\_4,+\_4)\\$.

### Task

Write a program or function that accepts a non-negative integer **n** as input and prints or returns the number of non-isomorphic groups of order **n**.

### Test cases

```
Input   Output
0       0
1       1
2       1
3       1
4       2
5       1
6       2
7       1
8       5
9       2
10      2
11      1
12      5
13      1
14      2
15      1
16      14
17      1
18      5
19      1
20      5

```

(taken from OEIS A000001)

### Additional rules

* There are no limits on execution time or memory usage.
* Built-ins that trivialize this task, such as Mathematica's `FiniteGroupCount`, are not allowed.
* Standard rules apply.

# Answer
# CJam, ~~189~~ 187 bytes

This one's gonna be tough to explain... Time complexity is guaranteed to be `O(scary)`.

```
qi:N_3>{,aN*]N({{:L;N,X)-e!{X)_@+L@@t}%{X2+<z{_fe=:(:+}%:+!},}%:+}fX{:G;N3m*{_~{G@==}:F~F\1m>~F\F=}%:*},:L,({LX=LX)>1$f{\_@a\a+Ne!\f{\:M;~{M\f=z}2*\Mff==}:|{;}|}\a+}fX]:~$e`{0=1=},,}{!!}?

```

If you're brave enough, try it online. On my crappy laptop I can get up to 6 with the Java interpreter or 5 in the online interpreter.

# Explanation

I don't have a big math background (just finished high school, starting CS at uni next week). So bear with me if I make mistakes, state the obvious, or do things in horribly inefficent ways.

My approach is a brute force, though I tried to make it a little more clever. The main steps are:

1. Generate all the possible operands  for a group of order **n** (i.e., enumerate all groups of order **n**);
2. Generate all the possible bijections **φ** between two groups of order **n**;
3. Using the results from steps 1 and 2, determine all isomorphisms between two groups of order **n**;
4. Using the result from step 3, count the number of groups up to isomorphism.

Before looking at the how each step is done, let's get some trivial code out of the way:

```
qi:N_             e# Get input as integer, store in N, make a copy
     3>{...}    ? e# If N > 3, do... (see below)
            {!!}  e# Else, push !!N (0 if N=0, 1 otherwise)

```

The following algorithm doesn't work correctly with **n \< 4**, the cases from 0 to 3 are handled with a double negation.

From now on, the elements of a group will be written as **{1, a, b, c, ...}**, where **1** is the identity element. In the CJam implementation, the corresponding elements are **{0, 1, 2, 3, ...}**, where **0** is the identity element.

Let's start from step 1. Writing all possible operators for a group of order **n** is equivalent to generating all the valid **n×n** Cayley tables. The first row and column are trivial: they are both **{1, a, b, c, ...}** (left-to-right, up-to-down).

```
      e# N is on the stack (duplicated before the if)
,a    e# Generate first row [0 1 2 3 ...] and wrap it in a list
  N*  e# Repeat row N times (placeholders for next rows)
    ] e# Wrap everything in a list
      e# First column will be taken care of later

```

Knowing that a Cayley table is also a reduced Latin square (due to the cancellation property) allows to generate the possible tables row-by-row. Starting from the second row (index 1), we generate all the unique *permutations* for that row, keeping the first column fixed to the value of the index.

```
N({                                 }fX e# For X in [0 ... N-2]:
   {                            }%      e#   For each table in the list:
    :L;                                 e#     Assign the table to L and pop it off the stack
       N,                               e#     Push [0 ... N-1]
         X)                             e#     Push X+1
           -                            e#     Remove X+1 from [0 ... N-1]
            e!                          e#     Generate all the unique permutations of this list
              {         }%              e#     For each permutation:
               X)_                      e#       Push two copies of X+1
                  @+                    e#       Prepend X+1 to the permutation
                    L@@t                e#       Store the permutation at index X+1 in L
                          {...},        e#     Filter permutations (see below)
                                  :+    e#   Concatenate the generated tables to the table list

```

Not all those permutations are valid, of course: each row and column must contain all the elements exactly one time. A filter block is used for this purpose (a truthy value keeps the permutation, a falsy one removes it):

```
X2+                 e# Push X+2
   <                e# Slice the permutations to the first X+2 rows
    z               e# Transpose rows and columns
     {        }%    e# For each column:
      _fe=          e#   Count occurences of each element
          :(        e#   Subtract 1 from counts
            :+      e#   Sum counts together
                :+  e# Sum counts from all columns together
                  ! e# Negate count sum:
                    e#   if the sum is 0 (no duplicates) the permutation is kept
                    e#   if the sum is not zero the permutation is filtered away

```

Note that I am filtering inside the generation loop: this makes the code a bit longer (compared to distinct generation and filtering), but greatly improves performance. The number of permutations of a set of size **n** is **n!**, so the shorter solution would require a lot of memory and time.

A list of valid Cayley tables is a great step towards enumerating the operators, but being a 2D structure, it can't check for associativity, which is a 3D property. So next step is filtering out non-associative functions.

```
{                                 }, e# For each table, keep table if result is true:
 :G;                                 e#   Store table in G, pop it off the stack
    N3m*                             e#   Generate triples [0 ... N-1]^3
        {                     }%     e#   For each triple [a b c]:
         _~                          e#     Make a copy, unwrap top one
           {    }:F                  e#     Define function F(x,y):
            G@==                     e#       x∗y (using table G)
                   ~F                e#     Push a∗(b∗c)
                     \1m>            e#     Rotate triple right by 1
                         ~           e#     Unwrap rotated triple
                          F\F        e#     Push (a∗b)∗c
                             =       e#     Push 1 if a∗(b∗c) == (a∗b)∗c (associative), 0 otherwise
                                :*   e#   Multiply all the results together
                                     e#   1 (true) only if F was associative for every [a b c]

```

Phew! Lots of work, but now we have enumerated all groups of order **n** (or better, the operations on it - but the set is fixed, so it's the same thing). Next step: find isomorphisms. An isomorphism is a bijection between two of those groups such that **φ(x ∗ y) = φ(x) ∗ φ(y)**. Generating those bijections in CJam is trivial: `Ne!` will do it. How can we check them? My solution starts from two copies of the Cayley table for **x ∗ y**. On one copy, **φ** is applied to all elements, without touching the order of rows or columns. This generates the table for **φ(x ∗ y)**. On the other one the elements are left as they are, but rows and columns are mapped through **φ**. That is, the row/column **x** becomes the row/column **φ(x)**. This generates the table for **φ(x) ∗ φ(y)**. Now that we have the two tables, we just have to compare them: if they are the same, we have found an isomorphism.

Of course, we also need to generate the pairs of groups to test isomorphism on. We need all the *2-combinations* of the groups. Looks like CJam has no operator for combinations. We can generate them by taking each group and combining it only with the elements following it in the list. Fun fact: the number of 2-combinations is **n × (n - 1) / 2**, which is also the sum of the first **n - 1** natural numbers. Such numbers are called triangular numbers: try the algorithm on paper, one row per fixed element, and you'll see why.

```
:L                          e# List of groups is on stack, store in L
  ,(                        e# Push len(L)-1
    {                  }fX  e# For X in [0 ... len(L)-2]:
     LX=                    e#   Push the group L[X]
        LX)>                e#   Push a slice of L excluding the first X+1 elements
            1$              e#   Push a copy of L[X]
              f{...}        e#   Pass each [L[X] Y] combination to ... (see below)
                            e#   The block will give back a list of Y for isomorphic groups
                    \a+     e#   Append L[X] to the isomorphic groups
                          ] e# Wrap everything in a list

```

The code above fixes the first element of the pair, **L\[X\]**, and combines it with other groups (let's call each one of those **Y**). It passes the pair to a isomorphism test block that I'll show in a moment. The block gives back a list of values of **Y** for which **L\[X\]** is isomorphic to **Y**. Then **L\[X\]** is appended to this list. Before understanding why the lists are set up in such a way, let's look at the isomorphism test:

```
\_@                                      e# Push a copy of Y
   a\a+                                  e# L[X] Y -> [L[X] Y]
       Ne!                               e# Generate all bijective mappings
          \f{                    }       e# For each bijection ([L[X] Y] extra parameter):
             \:M;                        e#   Store the mapping in M, pop it off the stack
                 ~                       e#   [L[X] Y] -> L[X] Y
                  {     }2*              e#   Repeat two times (on Y):
                   M\f=                  e#     Map rows (or transposed columns)
                       z                 e#     Transpose rows and columns
                                         e#     This generates φ(x) ∗ φ(y)
                           \Mff=         e#   Map elements of L[X], generates φ(x ∗ y)
                                =        e#   Push 1 if the tables are equal, 0 otherwise
                                  :|     e#   Push 1 if at least a mapping was isomorphic, 0 otherwise
                                    {;}| e#   If no mapping was isomorphic, pop the copy of Y off the stack

```

Great, now we have a list of sets like **\[{L\[0\], Y1, Y2, ...}, {L\[1\], Y1, ...}, ...\]**. The idea here is that, by transitive property, if any two sets have at least one element in common then all the groups in the two sets are isomorphic. They can be aggregated into a single set. As **L\[X\]** will never appear in the combinations generated by **L\[X+...\]**, after aggregating each set of isomorphisms will have one unique element. So, to get the number of isomorphisms, it's sufficient to count how many groups appear exactly once in all sets of isomorphic groups. To do this, I unwrap the sets so they look like **\[L\[0\], Y1, Y2, ..., L\[1\], Y1, ...\]**, sort the list to create clusters of the same group and finally RLE-encode it.

```
:~            e# Unwrap sets of isomorphic groups
  $           e# Sort list
   e`         e# RLE-encode list
     {    },  e# Filter RLE elements:
      0=      e#   Get number of occurrences
        1=    e#   Keep element if occurrences == 1
            , e# Push length of filtered list
              e# This is the number of groups up to isomorphism

```

That's all, folks.
> 17 votes

# Answer
# CJam, 73 bytes

```
0ri:Re!Rm*{:Tz0=R,=[R,Te_]m!{~ff{T==}e_}/=&},{:T,e!{:PPff{T==P#}}%$}%Q|,+

```

The time complexity of the above code is worse than **O(n!n)**.

Input **n=4** is already to much for the online interpreter.

Using the Java interpreter, input **n=5** could be possible, if you have enough RAM and patience.

### Finding groups

Given a group **(G, ∗)** of order **n**, we can pick an arbitrary bijection **φ : G -\> Cn** such that **φ(e) = 0**.

**φ** will become an isomorphism of **(G, ∗)** and **(Cn, ∗')** if we define **∗'** by **x ∗' y = φ(φ-1(x) ∗ φ-1(y))**.

This means that it suffices to study all group operators in **Cn** such that **0** is the neutral element.

We will represent a group operator  in **Cn** by a rectangular array **T** of dimensions **n × n** such that **T\[x\]\[y\] = x ∗ y**.

To generate such an array, we can start by picking a permutation of **Cn** for each of its **n** rows.

This way, **0** will be present in all *rows* (but not necessarily all *columns*), meaning that the third condition (existence of an inverse) will be fulfilled, whatever **e** may be.

We can fix **e = 0** by requiring that the first *column* of **T** is equal to **Cn**. In particular, the second condition (existence of a neutral element) will hold.

To verify that **T** corresponds to a group operator, all that's left to do is verifying that the first condition (associativity) holds. This can be done exhaustively by checking that **T\[T\[x\]\[y\]\]\[z\] == T\[x\]\[T\[y\]\[z\]\]** for all **x, y, z** in **Cn**.

### Counting non-isomorphic groups

The above method for finding groups will yield some isomorphic groups. Rather than identifying which ones are isomorphic, we generate the family of all isomorphic groups for every one of them.

This can done achieved by iterating over all bijections **φ : Cn -\> Cn**, and determining the associated array , defined by **Tφ\[x\]\[y\] = φ-1(T\[φ(x)\]\[φ(y)\])**.

All that's left to do is counting the number of distinct families.

### What the code does

```
0         e# Push 0. For input 0, the remaining code will crash, leaving
          e# this 0 on the stack.
ri:R      e# Read an integer from STDIN and save it in R.
e!        e# Push all permutations of [0 ... R-1].
Rm*       e# Push all arrays of 6 permutations of [0 ... R-1].
{         e# Filter; for each array:
  :T      e#   Save it in T.
  z0=R,=  e#   Check if the first column equals [0 ... R-1].
  [R,Te_] e#   Push [0 ... R-1] and a flattened T.
  m!{     e#   For both pairs (any order):
    ~     e#     Unwrap the pair.
    ff{   e#     For each X in the first: For each Y in the second:
      T== e#       Push T[X][Y].
    }     e#
  }/      e#
  =       e#   Check for equality, i.e., associativity.
  &       e#   Bitwise AND with the previous Boolean
},        e# Keep T iff the result was truthy.
{         e# For each kept array:
  :T      e#   Save it in T
  ,e!     e#   Push all permutations of [0 ... R-1].
  {       e#   For each permutation:
    :PP   e#     Save it in P. Push a copy.
    ff{   e#     For each X in P: For each Y in P:
      T== e#       Push T[X][Y].
      P#  e#       Find its index in P.
    }     e#
  }%      e#
  $       e#   Sort the results.
}%        e#
Q|,       e# Deduplicate and count.
+         e# Add the result to the 0 on the stack.

```
> 5 votes

# Answer
# Python 2, ~~515~~ 507 bytes

* Saved eight bytes thanks to Dennis.

```
def F(n):
 def f(k,*s):n==len(set(s))and S.add(s);{k and f(~-k,j,*s)for j in I}
 def c(k,*G):k and{s in G or c(~-k,s,*G)for s in S}or(I in G)&all((o(x,y)in G)&any(I==o(z,x)for z in G)for x in G for y in G)and A.add(G)
 S=set();A=S-S;I=tuple(range(n));o=lambda x,y:tuple(y[x[j]]for j in I);i=lambda G,H:any(all(o(H[B[i]],H[B[j]])==H[B[[k for k in I if G[k]==o(G[i],G[j])][0]]]for i in I for j in I)for B in S);f(n);c(n);K=list(A);[G in K and{G!=H and i(G,H)and K.remove(H)for H in K}for G in A];return len(K)

```

Try it online!

---

Using the equivalence between the number of non-isomorphic subgroups of order \\$n\\$ of \\$\ \Sigma\_n\\$ and the number of isomorphic equivalence classes of finite groups of order \\$n\\$.

Link to verbose version.
> 2 votes

---
Tags: code-golf, math, abstract-algebra
---


title: FIFO cache anomalies

text:
# Question
Title: FIFO cache anomalies
### This is the followup challenge from this one, if you're confused please check that one out first.

---

First, let \\$m(s, k)\\$ be the number of cache misses a sequence \\$s\\$ of resource accesses would have assuming our cache has capacity \\$k\\$ and uses a first-in-first-out (FIFO) ejection scheme when it is full.

Then given a ratio \\$r \> 1\\$, return a non-empty sequence of resources accesses \\$s\\$ such that there exists \\$k \> j\\$ with \\$m(s, k) \geq r \cdot m(s, j)\\$.

In plain English, construct a sequence \\$s\\$ of resource accesses so that there's two cache sizes where the bigger cache has (at least) \\$r\\$ times **more** cache misses when used to resolve \\$s\\$.

An example for \\$r = 1.1\\$, a valid output is the sequence \\$(3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4)\\$, as it causes \\$9\\$ cache misses for a cache size of \\$3\\$, but \\$10\\$ misses for a cache size of \\$4\\$.

It doesn't matter what sequence you return, as long as it meets the requirements.

---

Shortest code in bytes wins.

# Answer
> 7 votes
# Wolfram Language (Mathematica), ~~124~~ ~~113~~ 101 bytes

```
Flatten@{s=⌈2#⌉;q=Range[r=2s+1];g=Mod[q s-s,r];{Sort@g[[#+1;;]],g[[;;#]]}&~Array~r,Table[q,s^3]}&

```

Try it online!

NOTE: The TIO output is not the actual list because it would be very long. The wrapper function on TIO tells you the number of page faults for two cache capacities.

For the actual list: Try it online!

Related: arXiv:1003.1336

### How?

Let's assume a situation where we have two cache capacities, `3` and `4`.

Also, let's say the `3`-cache has `{4, 2, 5}` paged, and `4`-cache has `{5, 4, 3, 2}` paged. Then, let's try paging `{1, 2, 3, 4, 5, 1, 2, 3, 4, 5}`:

```
page  3-cache   4-cache
      {4,2,5}  {5,4,3,2}
  1   {1,4,2}  {1,5,4,3}
  2   {1,4,2}  {2,1,5,4}
  3   {3,1,4}  {3,2,1,5}
  4   {3,1,4}  {4,3,2,1}
  5   {5,3,1}  {5,4,3,2}
  1   {5,3,1}  {1,5,4,3}
  2   {2,5,3}  {2,1,5,4}
  3   {2,5,3}  {3,2,1,5}
  4   {4,2,5}  {4,3,2,1}
  5   {4,2,5}  {5,4,3,2}

```

The `3`-cache had 5 page faults, while the `4`-cache had 10. We also returned to our original state.

Here, if we repeat paging `{1, 2, 3, 4, 5}`, we would asymptotically reach the ratio of `2`.

We can extend this phenomenon to higher cache capacities so that we can page `{1, 2, 3, ... , 2n + 1}` and end up with any ratio.

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


title: Nonogram line brute-force solving

text:
# Question
Title: Nonogram line brute-force solving
# Background

Nonogram, also known as Picross or Griddlers, is a puzzle where the objective is to determine if each cell on the 2D grid should be colored or left blank, using the numbers of consecutive colored cells on each line.

The following is an example Nonogram puzzle with solution.

The problem is, some commercial Nonogram games/mobile apps have puzzles which are not solvable by hand (e.g. have multiple solutions, or require deep backtracking). However, they also offer some lives to the player, where **one life is lost when you try to color a cell whose correct answer is blank**. So now it's time to brute-force those nasty "puzzles"!

In order to simplify the task, imagine just one line with its clue and nothing else:

```
3 7 | _ _ _ _ _  _ _ _ _ _  _ _ _ _ _

```

The `[3,7]` are the clues, and the line length is 15 cells. Since it has multiple possible solutions, we need to risk some lives in order to fully solve this line (i.e. determine all colored cells).

# Challenge

Given a line with clues (a list of positive integers) and the line length, find the maximum number of lives you will lose, assuming that you brute-force the line with optimal strategy.

Note that **you always guess colored cells**. In actual games, guessing empty cells (either right or wrong) have no effect on your lives, so you can't "solve" the puzzle that way.

Also, you can assume the input always represents a valid Nonogram line, so you don't need to worry about something like `[6], 5`.

# Explanation

Let's look at some simpler examples first.

### `[1,2], 5`

There are exactly three possibilities for this line (`O` is a colored cell, `.` is an empty one):

```
O . O O .
O . . O O
. O . O O

```

If we try coloring cell 0 (0-based index from left), one of the following happens:

* The cell is correctly colored. Now we have two possibilities, and we can choose between cell 2 and cell 4 in order to fully solve the line. Either case, we will lose one life in the worst case.
* The cell is empty, and we lose a life. In this case, we have already identified the unique solution to this line, so we're done with 1 life lost.

Therefore, the answer for `[1,2], 5` is 1.

### `[5], 10`

Binary search? Nope.

The most obvious first choice is 4 or 5, which will reveal one possibility if it's blank (at a cost of 1 life). Let's say we chose 4 first. If cell 4 is indeed colored, we extend it to the left, i.e. try 3, 2, 1 and 0 until a life is lost (or cell 0 is colored, then we end up spending no lives at all). Whenever a life is lost, we can uniquely determine the solution, e.g. if we see something like this:

```
_ _ X O O _ _ _ _ _

```

then we already know the answer is this:

```
. . . O O O O O . .

```

Therefore, the answer for `[5], 10` is also 1.

### `[3,7], 15`

Start with cell 11, which, if empty, will reveal the following solution right away.

```
O O O . O O O O O O O X . . .

```

Then try 12, which, if empty, gives two possibilities which can be solved at the cost of 1 extra life.

```
O O O . . O O O O O O O X . .
. O O O . O O O O O O O X . .

```

Now try 2. If empty, it leads to three possibilities which can be solved similarly to the `[1,2], 5` example.

```
. . X O O O . O O O O O O O .
. . X O O O . . O O O O O O O
. . X . O O O . O O O O O O O

```

If you keep minimizing the risk in this manner, you can reach any solution with max. 2 lives spent.

# Test Cases

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

[2,1,1,3,1] 15 => 3
[1,1,1,2,1] 15 => 5

```

For the last two cases, the optimal strategy is *not* going through the minimum blanks, but simply going from left to right (or right to left). Thanks to @crashoz for pointing it out.

# Rules

Standard rules apply. The shortest valid submission in bytes wins.

# Bounty

If someone comes up with a polynomial-time algorithm (with the proof of correctness), I will award +100 bounty to such a solution.

# Answer
# Ruby, 85 bytes

```
f=->l,n,s=n-l.sum-l.size+1{*a,b=l;b&&s>0?(a[0]?1+f[a,n-b-2,s-1]:(n.to_f/b).ceil-1):0}

```

Try it online!

## Explanation

The first step is to establish a recursive divide and conquer strategy to solve subproblems. I will use the variables \\$l=\[l\_1,l\_2,...,l\_x\]\\$ for the list of clues, \\$x\\$ for the number of clues and \\$n\\$ for the number of cells.

Try to fit the last clue \\$l\_x\\$:
We test the cell at \\$n-l\_x\\$
**(1)** If it's empty: then all of the clues are before \\$n-l\_x\\$. So we lose a life and we call recursively \\$1+f(l,n-l\_x)\\$
**(2)** If it's colored: We are not sure how to place the last clue, so we test every cells to the right until finding an empty one The worst case is finding the empty cell at the last index, we lose a life, but we have placed the last clue so we can call recursively \\$1+f(\tilde{l},n-l\_x-2)\\$ where \\$\tilde{l}\\$ is \\$l\\$ without the last clue.

So we can get the number of lives with this function $$ f(l,n)=\begin{cases} 0, & \text{if } \sum\_1^xl\_i+x-1 \geq n\\ \lceil \frac{n}{l\_x} \rceil - 1 & \text{if } x= 1\\ 1+\max\begin{cases} f(l,n-l\_x)\\ f(\tilde{l},n-l\_x-2) \end{cases}, & \text{otherwise} \end{cases} $$

Here is an example `_` are unknown, `X` is a known space, `O` is a known colored cell and `L` is life lost

```
[2,2,4] 15                  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
(1) -> [2,2,4] 11           _ _ _ _ _ _ _ _ _ _ _ L X X X
    (1) -> [2,2,4] 7        _ _ _ _ _ _ _ L X X X L X X X
        0                   X X X L X X X L X X X L X X X
    (2) -> [2,2] 5          _ _ _ _ _ X O O O O L L X X X
        0                   O O X O O X O O O O L L X X X
(2) -> [2,2] 9              _ _ _ _ _ _ _ _ _ X O O O O L
    (1) -> [2,2] 7          _ _ _ _ _ _ _ L X X O O O O L
        (1) -> [2,2] 5      _ _ _ _ _ L X L X X O O O O L
            0               O O X O O L X L X X O O O O L
        (2) -> [2] 3        _ _ _ X O O L L X X O O O O L
            1               O O L X O O L L X X O O O O L
    (2) -> [2] 5            _ _ _ _ _ X O O L X O O O O L
        2                   O O L L X X O O L X O O O O L

```

It makes a binary tree, to get the number of lives lost, we just need to count the maximum height of the tree. However this makes it \\$\mathcal{O}(2^n)\\$ because we evaluate all of the branches. We can do better.

Let's define a cost function \\$h\\$ that will help us "choose" the right branch at each step.

$$ h(l,n)=n - \sum\_1^xl\_i-x+1 $$

\\$h\\$ counts the number of superfuous spaces we have if we pack all the clues with one space in between. So it is essentially an indicator of how much lives we are going to need to solve the instance, the higher it is, the more lives are necessary. The idea is to apply this indicator on our recursive formula.

By definition of \\$h\\$ we have, $$ \begin{align} h(l,n-l\_x) &= n - l\_x - \sum\_1^xl\_i-x+1\\ & =(n - \sum\_1^xl\_i-x+1) - l\_x\\ & = h(l,n) - l\_x \end{align} $$

And, $$ \begin{align} h(\tilde{l},n-l\_x-2) &= n - l\_x - 2 - \sum\_1^{x-1}l\_i-(x-1)+1\\ & =(n - \sum\_1^xl\_i-x+1) - 1\\ & = h(l,n) - 1 \end{align} $$

Then, $$ h(l,n)=\begin{cases} \leq 0, & \text{if } \sum\_1^xl\_i+x-1 \geq n\\ n - l\_x, & \text{if } x=1\\ \max\begin{cases} h(l,n-l\_x)+l\_x\\ h(\tilde{l},n-l\_x-2)+1 \end{cases}, & \text{otherwise} \end{cases} $$

We want to **maximize** \\$h\\$ at each step to get the worst case so let's check the difference between the two expressions in the recurrence

$$ \[h(l,n-l\_x)+l\_x\] - \[h(\tilde{l},n-l\_x-2)+1\]\\ \begin{align} &= n-l\_x-n - \sum\_1^xl\_i-x+1 + l\_x - \[n-l\_x-2 -\sum\_1^{x-1}l\_i-(x-1)+1+1\]\\ &=-2 \end{align} $$

$$ \begin{align} \[h(l,n-l\_x)+l\_x\] - \[h(\tilde{l},n-l\_x-2)+1\] &=-2\\ \[h(l,n-l\_x)+l\_x\] - \[h(\tilde{l},n-l\_x-2)+1\] &\< 0\\ \[h(l,n-l\_x)+l\_x\] &\< \[h(\tilde{l},n-l\_x-2)+1\] \end{align} $$ So the 2nd expression is always the max, we can remove the first one

$$ h(l,n)=\begin{cases} \leq 0, & \text{if } \sum\_1^xl\_i+x-1 \geq n\\ n - l\_x, & \text{if } x=1\\ h(\tilde{l},n-l\_x-2)+1 & \text{otherwise} \end{cases} $$

Finally this recursive definition of \\$h\\$ shows us that option **(2)** in function \\$f\\$ is always the worst case (giving the maximum number of possibilities i.e. maximizing \\$h\\$)

$$ f(l,n)=\begin{cases} 0, & \text{if } \sum\_1^xl\_i+x-1 \geq n\\ \lceil \frac{n}{l\_x} \rceil - 1 & \text{if } x= 1\\ 1+ f(\tilde{l},n-l\_x-2), & \text{otherwise} \end{cases} $$

Every step we decrease \\$n\\$ by at least 3 and there is now a single recursive call, complexity is \\$\mathcal{O}(n)\\$
> 21 votes

# Answer
## Python, ~~303~~ 289 bytes

First golf in a long time, so there may be a lot of excess fat. (Thanks Jo King for finding 14 bytes-worth.)

Function f generates all the possible arrangements (though always with a blank as the first character, but that's fine as long as we increment the length by 1 before we call it). Function g picks the position with the fewest number of blanks and recurses. Function h puts them together.

```
f=lambda l,n:["."*i+"X"*l[0]+c for i in range(1,n-l[0]+1)for c in f(l[1:],n-i-l[0])]if l else["."*n]
def g(q,n):O,X=min([[[p[:i]+p[i+1:]for p in q if p[i]==u]for u in".X"]for i in range(n)],key=lambda x:len(x[0]));return(len(q)>1)*1and max(1+g(O,n-1),g(X,n-1))
h=lambda l,n:g(f(l,n+1),n+1)

```

The examples all run fine:

```
>>> h([3,7],15)
2
>>> h([3,4],15)
3
>>> h([1,1,1,2,1],15)
6

```
> 2 votes

---
Tags: code-golf, puzzle-solver
---


title: 3... 2... 1... Crash off!

text:
# Question
Title: 3... 2... 1... Crash off!
Your task is to write a full program that will continue to count down from 10 every time it is run.

* The first time you run the program, it should print `10`.
* The next time, it should output `9`.
* The next time, it should output `8`, and so on.
* Instead of printing `0`, the program should crash. You do not have to handle the program running any more times after that.
* Any facilities used for storage may be assumed to be empty before the first execution of the program.

Here's an example implementation in Python 3:

```
try:f=open("a","r+");v=int(f.read())
except:f=open("a","w");v=10
1/v
print(v)
f.seek(0)
f.write(str(v-1))

```

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

# Answer
> 18 votes
# 6502 machine language + Apple \]\[+ ROM, 12 (11? 10? 9?) bytes

```
CE 06 80 F0 01 A2 0B A9 00 4C 24 ED

```

Should start at `$8000`. Crashes to the system monitor when the count reaches 0.

---

```
C6 B6 F0 01 A2 0B A9 00 4C 24 ED

```

Should start at `$B1`. This saves a byte since I can use the (two-byte) zero-page version of `DEC`, but overwrites the critical Applesoft routine `CHRGET`; you'll need to load it and call it from the monitor, and use `CTRL`+`B``Return` to re-initialize BASIC once you're done. Not sure if this invalidates it or not.

---

```
CE 06 80 F0 01 A2 0B 4C 26 ED

```

Should start at `$8000`. This doesn't initialize `$9E`, saving two bytes. However, this means you **must not call it with a negative address** (or, if you call it from the monitor, you have to call the monitor with a positive address). If you do, Applesoft's `CALL` routine will store `FF` in `$9E`, causing it to add 65280 to the number when printing it. Again, not sure if this invalidates the solution or not.

---

```
C6 B6 F0 01 A2 0B 4C 26 ED

```

Should start at `$B1`. This is a combination of the above two programs, saving a total of three bytes; you'll have to call the monitor with a positive address, load it and run it from there, and use `Ctrl`+`B``Return` to re-initialize BASIC once you're done.

---

Note that these programs only modify the program in memory; re-loading the program from disk will reset the countdown. This works because the Apple \]\[ (and \]\[+, //e, and //c) have no memory protection system whatsoever; the program (and its self-modifications) will stay in memory even after it exits, so you can keep running it from memory until you overwrite that memory with something else.

---

## Sample run

```
]BLOAD COUNT THEN BRK
]CALL 32768
10
]CALL 32768
9
]CALL 32768
8
]CALL 32768
7
]CALL 32768
6
]CALL 32768
5
]CALL 32768
4
]CALL 32768
3
]CALL 32768
2
]CALL 32768
1
]CALL 32768

8008-    A=80 X=9D Y=00 P=36 S=EE
*

```

---

## Explanation

```
     DEC NUM+1  ; Decrement the LDX instruction's operand
     BEQ NUM+1  ; If it is now zero, branch to it; 00 is the opcode for the BRK instruction, which causes the program to crash to the monitor
NUM  LDX #$0B   ; Load the X register with 0x0A; the operand has already been decremented once
     LDA #$00   ; Load the accumulator with 0
     JMP $ED24  ; Jump to $ED24, an Applesoft ROM routine which prints A (high byte),X (low byte) in decimal

```

---

## Explanation of 10 byte version

```
     DEC NUM+1  ; Decrement the LDX instruction's operand
     BEQ NUM+1  ; If it is now zero, branch to it; 00 is the opcode for the BRK instruction, which causes the program to crash to the monitor
NUM  LDX #$0B   ; Load the X register with 0x0A; the operand has already been decremented once
     JMP $ED26  ; Jump to $ED26, which is two bytes into the Applesoft routine at $ED24. The two skipped bytes would store the accumulator in $9E

```

---

# Variants

## Prints `ERR` and beeps when count reaches 0

### Normal - 15 bytes

```
CE 06 80 F0 07 A2 0B A9 00 4C 24 ED 4C 2D FF

```

### Overwrites `CHRGET` \- 14 bytes

```
C6 B6 F0 07 A2 0B A9 00 4C 24 ED 4C 2D FF

```

### Doesn't initialize `$9E` \- 13 bytes

```
CE 06 80 F0 05 A2 0B 4C 26 ED 4C 2D FF

```

### Overwrites `CHRGET` and doesn't initialize `$9E` \- 12 bytes

```
C6 B6 F0 05 A2 0B 4C 26 ED 4C 2D FF

```

---

## Freezes when count reaches 0

### Normal - 12 bytes

```
CE 06 80 F0 FE A2 0B A9 00 4C 24 ED

```

### Overwrites `CHRGET` \- 11 bytes

```
C6 B6 F0 FE A2 0B A9 00 4C 24 ED

```

### Doesn't initialize `$9E` \- 10 bytes

```
CE 06 80 F0 FE A2 0B 4C 26 ED

```

### Overwrites `CHRGET` and doesn't initialize `$9E` \- 9 bytes

```
C6 B6 F0 FE A2 0B 4C 26 ED

```

# Answer
> 35 votes
# Perl on Linux, 17 bytes

I thought it might be interesting to create a program that doesn't maintain any state itself, and doesn't modify its own source code; in other words, it actually checks how often it's been run by asking the OS. The question says "Any facilities used for storage may be assumed to be empty before the first execution of the program.", and thus we'd want to start from a completely blank OS. As such, I'd better explain just how you go about doing that, as otherwise testing the program is difficult.

There are actually two ways to set up for running the program. Either way, the minimal OS for the purpose would be running nothing but a shell (to enable us to run Perl in turn), and the simplest possible shell at that (so that it doesn't do anything fancy that makes the OS non-blank). `/bin/dash` is a good choice here, as it was intended as a minimal shell for system recovery. Then, we need to start Linux in such a way that it's running nothing but `dash`. We can either do this by rebooting the computer with `init=/bin/dash` on the Linux command line so that it starts nothing besides `dash`, or (much more conveniently) creating a Linux container using `unshare -Urfp /bin/dash` in a terminal (`unshare` doesn't actually *create* a blank OS, but it does *simulate* one; notably, the inside of the container thinks it's root, `dash` thinks it's init, etc., just as would happen on an actual blank OS). Disclaimer: I haven't actually tested this on bare metal yet, only inside `unshare`, but it should work both ways in theory.

Finally, once we've got that set up, we simply have to look at the PID; as we're on a blank system, the init system (here, the shell) will have PID 1, so the executions of Perl will have PIDs from 2 up to 12 inclusive. So our program looks like this:

```
say 12-$$||die

```

Here's a sample run:

```
$ unshare -Urfp /bin/dash
# perl -E 'say 12-$$||die'
10
# perl -E 'say 12-$$||die'
9
# perl -E 'say 12-$$||die'
8
# perl -E 'say 12-$$||die'
7
# perl -E 'say 12-$$||die'
6
# perl -E 'say 12-$$||die'
5
# perl -E 'say 12-$$||die'
4
# perl -E 'say 12-$$||die'
3
# perl -E 'say 12-$$||die'
2
# perl -E 'say 12-$$||die'
1
# perl -E 'say 12-$$||die'
Died at -e line 1.
#

```

# Answer
> 14 votes
# Bash \+ sed, ~~41~~ ~~40~~ 38 bytes

```
echo $[n=10/1]
sed -i s/$n/$[n-1]/g $0

```

Try it online!

# Answer
> 9 votes
## Javascript, 42 bytes

```
y=localStorage;y.a=y.a||10;alert(y.a--||a)

```

Test it out with this fiddle \- be sure to clear your local storage to reset the countdown.

Thanks to steenbergh, Lmis, and obarakon for lots of bytes!

# Answer
> 9 votes
# Dyalog APL, ~~33~~ ~~28~~ 22/20? bytes

I am not sure if this is valid, as it consists of a function (which must be called with a dummy argument). However, all APL programs (purely functional or not) have the same status, and indeed some APL versions do not have traditional programs, only functions. In compensation, I have added two bytes to name it, although that is not necessary for the desired effect.

```
f←{6::⊢c∘←10⋄÷÷c∘←c-1}

```

Note that this relies on an unofficial quirk, that `∘←` assigns globally.

`6::` upon any value error

`⊢c` return *c*

`∘←10` which is globally set to 10

now

`÷÷c` return the twice inverted (errors on zero) c

`∘←` which is globally set to

`c-1` one less than *c*

TryAPL online!

---

Certainly valid 28 byte version:

```
f
⍎'c←11'/⍨0=⎕NC'c'
⊢c←÷÷c-1

```

Works by setting *c* to 11 if missing, then subtracting 1 from *c*, inverting twice (which gives div-by-zero error if *c*-1 is 0), assigning to *c*, and outputting the new value.

---

Old 33 byte version:

```
f
÷÷≢2↓r⊣⎕FX¯1↓r←⎕NR'f'

```

Works by redefining itself on each run, but with one less trailing newline. Outputs the twice inverted number of remaining lines (less two), thus giving a div-by-zero error when only two lines are left (the header and the actual code).

# Answer
> 8 votes
## C#, ~~197~~ ~~160~~ ~~159~~ 125 bytes

```
namespace System.IO{class P{static void Main(){int n=11;for(;File.Exists(""+--n););File.Create(""+n);Console.Write(n*n/n);}}}

```

*Saved 34 bytes thanks to milk*

And a formatted version (With `ReadKey` added so you can view the output):

```
namespace System.IO
{
    class P
    {
        static void Main()
        {
            int n=11;
            for(;File.Exists(""+--n););
            File.Create(""+n);
            Console.Write(n*n/n);
        }
    }
}

```

It is longer than I thought it would be so there's probably room for golfing.

# Answer
> 7 votes
# Perl, ~~37~~ 36 bytes

```
9=~//;print$'-sysopen$~,$0,print$'+1

```

Crashes when the initial value reaches -1 (which would have printed 0), as it writes over the `=~` operator.

Saved a byte using `sysopen` rather than `open`. This allows me to print to `STDOUT` first, using the return value as the file mode (`1`, a.k.a. `O_WRONLY`), before `$~` is reassigned.

**Sample Usage**

```
$ perl crash-off.pl
10
$ perl crash-off.pl
9
$ perl crash-off.pl
8

...

$ perl crash-off.pl
2
$ perl crash-off.pl
1
$ perl crash-off.pl
syntax error at crash-off.pl line 1, near "1~"
Execution of crash-off.pl aborted due to compilation errors.

```

# Answer
> 6 votes
# Perl 6,  ~~60~~  58 bytes

```
put 10-$=finish.lines||die;
$*PROGRAM.open(:a).put;
=finish

```

```
open($*PROGRAM,a=>put 10-$=finish.lines||die).put
=finish

```

Needs newline character after `=finish`.

`die` can be replaced with `1/0`.

## Explanation:

It gets a list of lines after `=finish` (`$=finish.lines`) subtracts that from `10`, and if the result isn't `0` it prints it, otherwise it `die`s.

The last thing it does is open itself in append mode, and add another line to the end.

# Answer
> 6 votes
# Python 2, 65 bytes

```
f=open(__file__,"r+")
x=75-len(f.read())
x/x
print x
f.write('#')

```

Inspired by L3viathan's answer.

Can be reduced to 60 bytes if you can choose to name the file a single character like `x` and then replace `__file__` with `'x'`. In that case, replace `75` with `70`.

# Answer
> 4 votes
# Jolf, 20 bytes

```
γ-@▲lqΈ?␡γ?γaγ0₯I₯C1

```

Try it here! Errors when `0` is printed. Modifies the code. Explanation to come.

# Answer
> 4 votes
# Applesoft BASIC, 21 bytes (tokenized)

```
0  PRINT 9 + 1: CALL 2066: END : OR <CTRL-F><CTRL-H>`

```

Replace `<CTRL-F>` and `<CTRL-H>` with their literal versions. Note that this only modifies the program in memory; re-loading it from the disk will reset the countdown.

---

## Sample run

```
]RUN
10

]RUN
9

]RUN
8

]RUN
7

]RUN
6

]RUN
5

]RUN
4

]RUN
3

]RUN
2

]RUN
1

]RUN

?SYNTAX ERROR IN 0

```

---

## Explanation

`PRINT 9 + 1` does what you'd expect. `CALL 2066` calls the 6502 machine-language routine at memory location 2066, which is after `END :`. `END` halts the program so that the machine-language routine (which, to the Applesoft interpreter, is garbage) isn't executed.

The machine-language routine simply decrements the `9` in `PRINT 9 + 1`. Disassembly:

```
0812-   CE 06 08    DEC $0806
0815-   60          RTS

```

After the counter reaches 0, it is "decremented" to `/`; attempting to run the program will then cause a syntax error.

# Answer
> 4 votes
## \*\>\<\>, ~~20~~ 18 bytes

```
a1Fi:0(?b1-:?:1Fn;

```

This actually works on Linux (and whatever supports files named `\n` I guess). It creates a file named `\n` on first run and outputs `10`. It proceeds to output one less number on each subsquent run, except `0` where it crashes instead.

### Explanation

```
a1F                   open file named "\n"
   i:                 recieve input and duplicate it (-1 if empty)
     0(?b             if the file is empty, push 11 to the stack
         1-           subtract one
           :          duplicate the number
            ?:        if the number isn't 0, duplicate it again
              1F      save the number to the file
                n     output the number (crash if non-existant)
                 ;    exit

```

# Answer
> 4 votes
# PHP 57 bytes

```
echo$n=($f=file(f))?$f[0]:10?:die;fputs(fopen(f,w),--$n);

```

doesn´t really crash but exit (without counting down) when it hits `0`. Is that sufficient?

Run with `-r`.

# Answer
> 4 votes
# C#, 156 bytes

I golfed @TheLethalCoder's answer for a bit, and was able to save 3 bytes by reordering the statements and eliminating the int.parse(). Still room for improvement, I'm sure.

```
using System.IO;class P{static void Main(){int n;try{n=File.ReadAllText("f")[0]-48;}catch{n=10;}System.Console.Write(n/n*n);File.WriteAllText("f",""+--n);}}

```

Ungolfed:

```
using System.IO;
class P
{
    static void Main()
    {
        int n;
        try
        {
            n = File.ReadAllText("f")[0] - 48;
        }
        catch {
            n = 10;
        }
        System.Console.Write(n / n * n);
        File.WriteAllText("f", "" + --n);
    }
}

```

Meta-question: It may be hack-y to take TheLethalCoder's work as a starting point for my answer. Would it be better (once I have the rep) to add this as a comment on their answer? I'm not trying to compete with them, I just want to show off my golf, for mutual edification.

# Answer
> 3 votes
## Ruby, ~~94~~ ~~87~~ ~~84~~ ~~61~~ 59 bytes

```
j=File.open(?a,"a+");1/(i=j.readlines.size-14);p -i;j.puts

```

Please leave suggestions below.

Thanks @ConorO'Brien for the ideas (some shamelessly ripped off from his answer).

# Answer
> 3 votes
## JavaScript, 74 bytes

~~`x=typeof x!=typeof 1?10:x!=1?x-=1:_`~~

`l=localStorage;l.a=typeof l.a!=typeof""?10:l.a!=1?l.a=--l.a:_;alert(l.a)`

# Answer
> 3 votes
## Powershell V2.0, 49 bytes

(First ever code golf, couldn't find the rules on how to calculate bytes. I used a String to bytes calculator online)

```
if(!$n){$n=10;$n}else{$n-=1;if($n-eq0){throw};$n}

```

Running:

```
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
10

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
9

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
8

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
7

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
6

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
5

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
4

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
3

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
2

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
1

____________________________________________________________________________________________________________________________________________________________________
PS C:\Users\***> if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw};$n;}
ScriptHalted
At line:1 char:49
+ if(!$n){$n = 10;$n}else{$n=$n-1;if($n-eq0){throw <<<< };$n;}
    + CategoryInfo          : OperationStopped: (:) [], RuntimeException
    + FullyQualifiedErrorId : ScriptHalted

```

# Answer
> 3 votes
## Java, 343 bytes

My first golfing attempt

```
import java.io.PrintWriter;class M{public static void main(String[] a) throws Exception{if(!new java.io.File("x").exists()) try(PrintWriter p=new java.io.PrintWriter("x")){p.write("10");}int b=new java.util.Scanner(new java.io.File("x")).nextInt();try(PrintWriter p=new java.io.PrintWriter("x")){p.print(b/b*b-1+"");System.out.print(b+"");}}}

```

ungolfed

```
import java.io.PrintWriter;

class M {
    public static void main(String[] a) throws Exception {
        if (!new java.io.File("x").exists()) {
            try (PrintWriter p = new java.io.PrintWriter("x")) {
                p.write("10");
            }
        }
        int b = new java.util.Scanner(new java.io.File("x")).nextInt();
        try (PrintWriter p = new java.io.PrintWriter("x")) {
            p.print(b / b * b - 1 + "");
            System.out.print(b + "");
        }
    }
}

```

# Answer
> 3 votes
# SQLite, ~~142~~ 137

This could probably be done much more cleverly. ~~141~~ 136 chars for code:

```
create table if not exists t(n not null);insert into t select 11;update t set n=case n when 1 then null else n-1 end;select min(n)from t

```

Plus 1 for the filename `x` in `sqlite3 x '…'`.

# Answer
> 2 votes
# Ruby, 52 + 1 = 53 bytes

Assumes the file is named `a` (+1 byte).

```
q=File.read ?a
0/h=62-q.size
p h
File.write ?a,q+?1#

```

## Running

```
C:\Users\Conor O'Brien\Documents\Programming
λ type a
q=File.read ?a
0/h=62-q.size
p h
File.write ?a,q+?1#
C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
10

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
9

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
8

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
7

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
6

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
5

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
4

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
3

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
2

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
1

C:\Users\Conor O'Brien\Documents\Programming
λ ruby a
a:2:in `/': divided by 0 (ZeroDivisionError)
        from a:2:in `<main>'

```

# Answer
> 2 votes
# Python 2, 89 bytes

```
x=10
x/x
print x
f=open(__file__,"r+")
s=f.read()
f.seek(0)
f.write(s.replace(`x`,`x-1`))

```

# Answer
> 2 votes
# JavaScript, 41

`l=localStorage;l.l=-~l.l;alert(11-l.l||I)`

# Answer
> 2 votes
# TI-BASIC (TI-84 Plus) (15 bytes)

```
If not(Ans
11
Ans-1
AnsAns/Ans

```

Ans should equal 0 (the default value) before the first run.

Since `AnsAns/Ans` is the last line of the program, it will be outputted and stored to Ans unless Ans is 0, in which case a divide by 0 error occurs.

# Answer
> 1 votes
# GNU Smalltalk, ~~70~~, 68 bytes

66 bytes code +2 bytes for the "-S" flag

EDITS

* Removed unnecessary parentheses, -2 bytes

**Golfed**

```
X=Y ifTrue:[Smalltalk at:#X put:10]ifFalse:[X:=X-1].(X*X/X)printNl

```

**Test**

```
>seq 11|xargs -L1 sudo gst -S fail.st 2>/dev/null
10
9
8
7
6
5
4
3
2
1
Object: 0 error: The program attempted to divide a number by zero
ZeroDivide(Exception)>>signal (ExcHandling.st:254)
SmallInteger(Number)>>zeroDivide (SysExcept.st:1426)
SmallInteger>>/ (SmallInt.st:277)
UndefinedObject>>executeStatements (fail.st:1)

```

*Important*

You must run *gst* as root, for it to be able to modify the default image, or specify your own image with *-I*.

# Answer
> 1 votes
# PHP, 45 bytes

Honestly not sure if this one counts.

```
<?session_start();echo10-$_SESSION[0]++?:die;

```

I'd post a link to an example, but all the online testers that I know don't allow `session_start()` to be used.

This will keep counting down each time you refresh the page until 0, when the `die` command is ran.

# Answer
> 0 votes
## QBIC, 70 bytes

```
open"r",1,"a.b" $get#1,1,e|~e=0|e=z\e=e-1]?e~e=0|$error 1|]$put#1,1,e|

```

Opens file `a.b` (or creates it when not found on first run), reads record 1 into `e`. If that record is not found, assume 10, else sub 1. At `e==0`, raise an error. Write back `e` to `a.b`.

File access is not built into QBIC, this relies heavily on the underlying QBasic.

# Answer
> 0 votes
## Batch, 72 bytes

```
@call:l
@if %n%==0 goto g
@echo %n%
@cmd/cset/a-1>>%0
:l
@set/an=10

```

Needs to be invoked using the full file name including extension. Last line must not have a trailing newline. Works by writing `-1` to the end of the last line so that it evaluates to 1 less each time. `goto g` errors out because there's no label `:g`.

# Answer
> 0 votes
## R, 52 bytes

```
`if`(!"x"%in%ls(),cat(x<-10),`if`(x>0,cat(x<-x-1),))

```

Essentially uses `ls()` to list the names of all globally stored objects. If we assume that the global environment is empty and `"x"` doesn't exist already, generate `x=10`, else if `x!=0` subtract `1` else call a missing argument which returns an error.

# Answer
> 0 votes
## Windows Batch, 61 bytes

```
@if %n%.==. set n=10
@if %n%==0 goto.
@set /a n-=1&@echo %n%
```

# Answer
> 0 votes
**JavaScript, 44 bytes**

```
function* f(n=11){for(;--n;yield n);throw''}

p=f()
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
console.log(p.next().value)
```

---
Tags: code-golf, stateful
---


title: Write a Shape Simplifier

text:
# Question
Title: Write a Shape Simplifier
# Introduction

I have a lot of ASCII rocks. They are built with dashes, pipes, Vs, carets, angle brackets, slashes and spaces. Example:

```
/--\
|  |
|  |
\--/

```

I want to erode them, like this:

```
 /\
/  \
\  /
 \/

```

All of the corners have become rounder. A more complicated example:

```
/----\
|     \------\
|            |
|            |
\------------/

 /--\
/    \------\
|            \
\            /
 \----------/

```

After another erosion, it would become

```
  /\
 /  \------\
<           \
 \          /
  \--------/

```

And another:

```
  /\------\
 <         \
  \        /
   \------/

```

# Challenge

Your challenge is to write a program that can erode an input once. You can assume there is only one rock and you can assume it is one closed loop. The input will only contain the chars `/\ -| <> ^V \n` and will have trailing spaces to create a rectangle. The program can either get input from STDIN and output to STDOUT or can be a function. At the end of each row is a newline character. The erosion must follow the rules outlined below (Note: in the examples the rock isn't completed, this is for ease of explanation). The output must be in the same format as the input, with the same size as the input. However, trailing spaces may be omitted.

The slashes will spread to pipelines and dashes and move across.

```
/---
|
|

 /--
/
|

  /-
 /
/

```

If two slashes merge together, the appropriate character out of `<>^V` is used.

```
/-----\
|     |
|     |
|     |
\-----/

 /---\
/     \
|     |
\     /
 \---/

  /-\
 /   \
<     >
 \   /
  \-/

   ^
  / \
 <   >
  \ /
   V

```

If a part of the rock can merge, it will. Note: if one part can merge but the other can't (i.e, `/\` in the second line of the example), then the one that can merge will (see example).

```
          /\
 /\-^-/\-/  \--
 |
 <
 |
 /
 \
 |
 /
/
\
 \
 |
 |

  /-------/\--
 /
 |
 |
 |
 |
 |
 |
 /
 \
 |
 |
 |

```

Eventually, all rocks will become nothing.

```
<>  ^  /\
    V  \/

```

# Test cases

Test 1:

```
/----\
|     \------\
|            |
|            |
\------------/

 /--\
/    \------\
|            \
\            /
 \----------/

  /\
 /  \------\
<           \
 \          /
  \--------/

  /\------\
 <         \
  \        /
   \------/

   /-----\
  <       \
   \      /
    \----/

    /---\
   <     \
    \    /
     \--/

     /-\
    <   \
     \  /
      \/

      ^
     < \
      \/

```

Test 2:

```
/----\
|    |
|    |
|    |
|    |
\----/

 /--\
/    \
|    |
|    |
\    /
 \--/

  /\
 /  \
/    \
\    /
 \  /
  \/

  /\
 /  \
 \  /
  \/

  /\
  \/

```

Test 3:

```
          ^    /\
 /\--/\--/ \--/  \-\
 \                 |
 |                 |
 /                 |
 \                 |
 |                 |
 |                 |
 /                 |
<                  |
 \                 |
 |                 |
 |                 |
 /                 |
/                  |
\                  |
 \-----------------/

  /-------^----/\-\
 /                 \
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 <                 |
 |                 |
 |                 |
 |                 |
 |                 |
 /                 |
 \                 /
  \---------------/

   /-------------\
  /               \
 /                 \
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 \                 /
  \               /
   \-------------/

    /-----------\
   /             \
  /               \
 /                 \
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 \                 /
  \               /
   \             /
    \-----------/

     /---------\
    /           \
   /             \
  /               \
 /                 \
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 |                 |
 \                 /
  \               /
   \             /
    \           /
     \---------/

      /-------\
     /         \
    /           \
   /             \
  /               \
 /                 \
 |                 |
 |                 |
 |                 |
 |                 |
 \                 /
  \               /
   \             /
    \           /
     \         /
      \-------/

       /-----\
      /       \
     /         \
    /           \
   /             \
  /               \
 /                 \
 |                 |
 |                 |
 \                 /
  \               /
   \             /
    \           /
     \         /
      \       /
       \-----/

        /---\
       /     \
      /       \
     /         \
    /           \
   /             \
  /               \
 /                 \
 \                 /
  \               /
   \             /
    \           /
     \         /
      \       /
       \     /
        \---/

         /-\
        /   \
       /     \
      /       \
     /         \
    /           \
   /             \
  /               \
  \               /
   \             /
    \           /
     \         /
      \       /
       \     /
        \   /
         \-/

          ^
         / \
        /   \
       /     \
      /       \
     /         \
    /           \
   /             \
   \             /
    \           /
     \         /
      \       /
       \     /
        \   /
         \ /
          V

          ^
         / \
        /   \
       /     \
      /       \
     /         \
    /           \
    \           /
     \         /
      \       /
       \     /
        \   /
         \ /
          V

          ^
         / \
        /   \
       /     \
      /       \
     /         \
     \         /
      \       /
       \     /
        \   /
         \ /
          V

          ^
         / \
        /   \
       /     \
      /       \
      \       /
       \     /
        \   /
         \ /
          V

          ^
         / \
        /   \
       /     \
       \     /
        \   /
         \ /
          V

          ^
         / \
        /   \
        \   /
         \ /
          V

          ^
         / \
         \ /
          V

          ^
          V

```

# Scoring

This is , so the program with the smallest number of bytes wins!

Standard loopholes are not allowed.

# Answer
# Rust

I gave up on this after a while, the instructions kind of seem ambiguous. However i did get some shrinky-looking rocks (see output). I also am pretty sure this needs to be done in a 2 dimensional space rather than in a 1 dimensional string as i tried here. My main "issue" is that I transform the given input by marking space as 'inside' or 'outside' the rock, unfortunately at this point it cannot distinguish between inside and the top/bottom edges.

```
enum State {
 OutsideLeft,CrossLI,Inside,CrossRI,OutsideRight,
}

const INPUT: &str = r#"
/----\
|     \------\
|            |
|            |
\------------/
"#;

fn precycle( mut data:Vec<char> ) -> Vec<char> {
    let mut state = State::OutsideLeft;
    let mut curcol = 0;
    let mut curline:Vec<char> = Vec::new();
    let mut lastline:Vec<char> = Vec::new();
    for mut i in 0..data.len() {
        if data[i]=='\n' {
            lastline = curline.to_vec();
            lastline.push(' ');
            curline.clear();
            curline.push(' ');
            curcol = 0;
        } else {
            curline.push(data[i]);
            curcol += 1;
        }
        let n = curcol%lastline.len();
        let n2 = lastline.len()-n;
        //println!("[{}]",lastline.iter().collect::<String>());
        //println!("[{}]",curline.iter().collect::<String>());
        //println!("({}{})({}{})>",data[i],state,lastline[n],curline[n]);
        //print!("{}{}>",data[i],state);
        match state {
        State::OutsideLeft  =>  {
            if      data[i]=='/' { state = State::CrossLI; }
            else if data[i]=='\\' { state = State::CrossLI; }
            else if data[i]=='|' { state = State::CrossLI; }
            else if data[i]=='<' { state = State::CrossLI; }
            if      data[i]==' ' { }
        } State::CrossLI => {
            if      data[i]=='/' { state = State::CrossRI; }
            else if data[i]=='\\' { state = State::CrossRI; }
            else if data[i]=='|' { state = State::CrossRI; }
            else if data[i]=='>' { state = State::CrossRI; }
            if data[i]==' ' { data[i]='-'; }
            if data[i]=='-' { state = State::Inside; }
        } State::Inside => {
            if      data[i]=='/' { state = State::CrossRI; }
            else if data[i]=='\\' { state = State::CrossRI; }
            else if data[i]=='|' { state = State::CrossRI; }
            else if data[i]=='>' { state = State::CrossRI; }
            if      data[i]==' ' { data[i] = '-'; }
        } State::CrossRI => {
            if  data[i]==' ' { state = State::OutsideRight; }
            if  data[i]=='\n' { state = State::OutsideLeft; }
        } State::OutsideRight => {
            if  data[i]==' ' { }
            if  data[i]=='\n' { state = State::OutsideLeft; }
        } }
        match state {
        State::CrossLI => {
            if curline[n]=='|' && lastline[n]=='.' { data[i]='9'; curline[n]='9'; }
        }
        State::CrossRI => {
            if curline[n]=='|' && lastline[n]=='.' { data[i]='8'; curline[n]='8'; }
            if curline[n]=='.' && lastline[n]=='8' { data[i-n-n2+1]='>'; }
            if curline[n]=='.' && lastline[n]=='|' { data[i-n-n2+1]='6'; }
        }
        State::OutsideLeft => {
            if curline[n]=='.' && lastline[n]=='|' { data[i-n-n2+1]='7'; curline[n] = '7'; }
            if curline[n]=='.' && lastline[n]=='9' { data[i-n-n2+1]='<'; }
        }
        _ => { }
        }
        //print!("{} ",state);

    }
    for mut i in 0..data.len() {
        if data[i]=='9' {data[i]='/'}
        if data[i]=='8' {data[i]='\\'}
        if data[i]=='7' {data[i]='\\'}
        if data[i]=='6' {data[i]='/'}
    }
    data
}

fn cycle( data:String ) -> String {
    data
    .replace(r#"^"#,r#"."#)
    .replace(r#"V"#,r#"."#)
    .replace(r#"/-\"#,r#".^."#)
    .replace(r#"\-/"#,r#".V."#)
    .replace(r#"-/\-"#,r#"----"#)
    .replace(r#"-\/-"#,r#"----"#)
    .replace(r#"/\-"#,r#"/--"#)
    .replace(r#"-/\"#,r#"--\"#)
    .replace(r#"\/-"#,r#"\--"#)
    .replace(r#"-\/"#,r#"--/"#)
    .replace(r#"./\."#,r#"...."#)
    .replace(r#".\/."#,r#"...."#)
    .replace(r#"/\"#,r#".."#)
    .replace(r#"\/"#,r#".."#)
    .replace(r#"-\"#,r#"\."#)
    .replace(r#"-/"#,r#"/."#)
    .replace(r#"/-"#,r#"./"#)
    .replace(r#"\-"#,r#".\"#)
    .replace(r#"->"#,r#">."#)
    .replace(r#"<-"#,r#".<"#)
    .replace(r#".-"#,r#"--"#)
    .replace(r#"-."#,r#"--"#)
}

fn main() {
    let mut inputv: Vec<char> = INPUT.chars().collect();
    let mut input0: Vec<char> = inputv;
    for j in 1..18 {
        let mut inputa = precycle( input0 );
        let pdata = inputa.iter().collect::<String>().replace("."," ");
        println!("{}",pdata);
        let mut input2 = cycle( inputa.iter().collect::<String>() );
        input0 = input2.chars().collect();
    }
}

```

output

```
/----\
|-----\------\
|------------|
|------------|
\------------/

 /--\
/----\------\
|------------\
\------------/
 \----------/

  /\
 /--\------\
<-----------\
 \----------/
  \--------/

  /\------\
 <---------\
  \--------/
   \------/

   /-----\
  <-------\
   \------/
    \----/

    /---\
   <-----\
    \----/
     \--/

     /-\
    <---\
     \--/
      \/

      ^
     <-\
      \/

     <\

     <\

     <\

     <\

     <\

     <\

     <\

     <\

     <\

```
> 1 votes

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


title: Help me fill my wallet!

text:
# Question
Title: Help me fill my wallet!
A while ago I purchased a new wallet which is able to hold 8 cards (4 on both side). However, I seem to have way more cards than that and I need to make choices on which ones I want to carry with me. Some cards I use more often than others, but the cards I prefer to carry with me are not necessarily the ones I use most.

## The challenge

Given a stack of cards, return the layout of my wallet in the best way possible w.r.t. my preferences and restrictions. The layout should be as follows:

```
__ __ (row 1)
__ __ (row 2)
__ __ (row 3)
__ __ (row 4)

```

Currently I posess the following cards - stacks will always consist of a selection from these:

* *1* identity card (**ID**)
* *1* driver's license (**DL**)
* *2* credit cards (**CC**)
* *5* debit cards (**DC**)
* *1* public transport card (**PC**)
* *1* gym access card (**GC**)
* *9* membership cards from random stores and warehouses (**MC**)

I have some preferences and restrictions:

* Cards sorted by priority: **ID, DL, CC, DC, PC, GC, MC**
* Cards sorted by usage frequency: **CC, DC, PC, GC, MC, ID, DL**
* For safety reasons, the total number of debit cards and credit cards in my wallet can be at most 1 more than the sum of all other cards that will go in my wallet ( *N*DC+*N*CC*N*ID+*N*DL+*N*PC+*N*GC+*N*MC+1 ).
* If present, my identity card and driver's licence should always go in row 1. This does not mean that other cards may not occupy spots in row 1.
* The most frequently used cards from the stack should always go in row 4.

## Rules

* No 2 cards can occupy the same spot.
* Higher priority cards are always prefered over lower priority ones, unless the DC/CC restriction kicks in.
* ID/DL at row 1 overrules the frequency rule: if only ID is provided, it will go in row 1 and row 4 will be empty!
* Input formatting can be done in any way you like, as long as the order of the input stack is retained. e.g. `ID,CC,PC,MC,MC,MC,DL` may also be supplied as e.g. `1ID 1CC 1PC 3MC 1DL 0DC 0GC` or `ID CC PC MC MC MC DL`.
* Output formatting does have a few restrictions: rows must all start at a new line, columns must be delimited in some way. Empty spots may be presented any way you like, as long as it does not mess up the 4x2 layout.
* There can be more than one solution/order, it's up to you which one you provide as output.
* You may assume that cards of the same type will always be grouped at input.
* Apart from the above, standard rules and loopholes apply.

## Bonus

You are allowed to remove **15%** of your bytecount if you also return any cards that did not go in the wallet. Print "It fits!" in case of no remaining cards. This additional output should be clearly separated from the returend layout.

## Examples

Input:

```
ID, DL, CC, GC, MC

```

2 possible outputs:

```
ID DL      DL ID
__ __  or  __ MC
MC __      __ __
CC GC      GC CC

optional: It fits!

```

---

Input:

```
ID, CC, DC, PC, GC, MC, MC, MC, MC, MC

```

2 possible outputs:

```
ID MC      GC ID
MC MC  or  MC PC
PC GC      MC MC
CC DC      DC CC

optional: e.g. (MC, MC)  or  (2MC)

```

---

Input:

```
DC, DC, CC, CC, GC, DL

```

2 possible outputs:

```
DL __      GC DL
__ __  or  DC __
GC DC      __ __
CC CC      CC CC

optional: e.g. (DC)  or  (1DC)

```

---

Input:

```
CC, DC, DC, DC

```

2 possible outputs:

```
__ __      __ __
__ __  or  __ __
__ __      __ __
CC __      __ CC

optional: e.g. (DC, DC, DC)  or  (3DC)

```

---

Input:

```
CC, CC, MC, MC, MC, MC, MC, MC, PC, DC, DC, DC, DC, DC, GC

```

2 possible outputs:

```
MC MC      MC DC
PC GC  or  DC GC
DC DC      PC MC
CC CC      CC CC

optional: e.g. (DC, DC, DC, MC, MC, MC, MC)  or  (3DC, 4MC)

```

---

Input:

```
MC, MC, MC, MC, MC, MC, MC

```

2 possible outputs:

```
__ MC      MC MC
MC MC  or  MC MC
MC MC      MC __
MC MC      MC MC

optional: It fits!

```

---

Input:

```
ID, CC

```

2 possible outputs:

```
ID __      __ ID
__ __  or  __ __
__ __      __ __
CC __      CC __

optional: It fits!

```

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

# Answer
> 6 votes
# Java 10, ~~385~~ ~~384~~ ~~382~~ 381 bytes

```
C->{String[]R=new String[8],F={"CC","DC","PC","GC","MC"};int c=C.size(),i=1,s=0;c=c>8?8:c;for(var q:C)if("DCC".contains(q))s++;for(;s+--s>c;c=(c=C.size())>8?8:c)i=C.remove(F[i])?i:0;for(c=0,i=8;i>0&c<5;c++)for(;i>0&C.remove(F[c]);)R[--i]=F[c];if(C.remove("ID"))R[c=0]="ID";if(C.remove("DL"))R[c<1?1:0]="DL";for(i=0;i<8;)System.out.print((R[i]!=null?R[i]:"__")+(i++%2>0?"\n":" "));}

```

Although it wasn't too difficult, I can see why it was unanswered. Especially that rule regarding \\$N\_{DC}+N\_{CC}\leq N\_{ID}+N\_{DL}+N\_{GC}+N\_{MC}+1\\$ costs quite a lot of bytes at the moment..
And since it's been about 2.5 year since this challenge has been posted, OP might have got another wallet by now anyway.. ;p

-1 byte thanks to *@Jakob*
-1 byte thanks to *@ceilingcat*

Try it online.

**Explanation:**

```
C->{                        // Method with String-List parameter and String return-type
  String[]R=new String[8],  //  String-array of size 8
          F={"CC","DC","PC","GC","MC"};
                            //  Frequency-order String-array
  int c=C.size(),           //  Size of the input-List
      i=1,                  //  Index integer, starting at 1
      s=0;                  //  Count-integer, starting at 0
  c=c>8?8:c;                //  If the size is larger than 8, set it to 8
  for(var q:C)              //  Loop over the cards of the input-List:
    if("DCC".contains(q))   //   If the card is a DC or CC:
      s++;                  //    Increase the counter by 1
  for(;s+--s>c;             //  Loop as long as the amount of DC/CC is larger than the
                            //  other amount of cards + 1:
      c=(c=C.size())>8?8:c) //    Recalculate the size after every iteration
    i=C.remove(F[i])?i:0;   //   If the List still contains a DC, remove it
                            //   Else: remove a CC instead
  for(c=0,                  //  Reset `c` to 0
      i=8;i>0               //  Loop as long as there is still room in the wallet,
      &c<5;                 //  and we still have cards left:
      c++)                  //    Go to the next card-type after every iteration
    for(;i>0                //   Inner loop as long as there is still room in the wallet,
        &C.remove(F[c]);)   //   and we still have a card of the current type left:
      R[i--]=F[c];          //    Put a card of the current type in the wallet
  if(C.remove("ID"))R[c=0]="ID";
                            //  Add the 'ID' card to the first row if present
  if(C.remove("DL"))R[c<1?1:0]="DL";
                            //  Add the 'DL' card to the first row if present
  for(i=0;i<8;)             //  Loop over the wallet:
    System.out.print(       //   Print:
      (R[i]!=null?          //    If the current slot contains a card:
        R[i]                //     Append this card
       :                    //    Else:
        "__")               //     Append an empty slot ("__")
      +(i++%2>0?"\n":" "));}//    Append the correct delimiter (space or new-line)

```

---

# Java 10, ~~390.15~~ 389.3 (458 bytes - 15% bonus)

```
C->{String r="",R[]=new String[8],F[]={"CC","DC","PC","GC","MC"},t=r;int c=C.size(),i=1,s=0;for(var q:C)if("DCC".contains(q))s++;for(;s+--s>(c>8?8:c);c=C.size())if(C.remove(F[i]))t+=F[i]+",";else i=0;for(c=0,i=8;i>0&c<5;c++)for(;i>0&&C.remove(F[c]);)R[--i]=F[c];if(C.remove("ID")){t+=R[0]+",";R[c=0]="ID";};if(C.remove("DL")){t+=R[c=c<1?1:0]+",";R[c]="DL";}for(i=0;i<8;)r+=(R[i]!=null?R[i]:"__")+(i++%2>0?"\n":" ");return r+"\n"+(C.size()>0?t+C:"It fits!");}

```

Try it online.

---
Tags: code-golf, string, sequence, sorting
---