title: 2D Maze Minus 1D

text:
# Question
Title: 2D Maze Minus 1D
This challenge is about converting 2D mazes into 1D mazes.

# Overview

```
+-+-+-+-+-+-+   +-+-+-+-+-+-+                    graph {
| |   |     |   |A|   |    B|   A         B        A -- D
+ + + + +-+-+   + + + + +-+-+    \        |        C -- D
|   | |     |   |   | |     |     \       |        D -- E
+-+-+ +-+-+ +   +-+-+ +-+-+ +      \      |        E -- F
|           |   |C   D E   F|   C---D-E---F        E -- G
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |   |        B -- F
|         | |   |      G  | |     .---G   |        F -- J
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /    |        G -- H
| |       | |   |H|I      |J|   H I-'     J        G -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)        } // (graphviz dot)
   Figure 1       Figure 2                 Figure 3

```

For the purposes of this challenge, a traditional 2D maze is a rectangular maze formed from lattice points where all of the following holds:

* It is closed (the outer rim is connected by walls).
* All lattice points are connected to walls
* It is connected (for every two spaces X and Y there is a path between them)
* It is acyclic (there are no paths from any space X back to X without backtracking)

Figure 1 shows a traditional 2D maze. These mazes have three areas of interest:

* *Dead ends* \- places from which there is only one available path
* *Corridors* \- places from which there are two available paths
* *Decision points* \- places from which there are three or four available paths

For every such maze, one can create a graph where the dead ends and decision points are nodes, and there is an edge between every two nodes connected by a path along a corridor. Figure 2 shows the same maze with such nodes labeled, and Figure 3 the maze's graph (in ASCII and Graphviz dot notation).

## 1D mazes

1D mazes incorporate warp points, which come in pairs, and are identified using a letter (in either case). Figure 4 shows an example 1D maze. This is otherwise identical to a 2D maze with a height of 1, as shown in Figure 5. Note in particular in Figure 5 the lattice point positions marked by `+`, which alternate left to right; in the 1D maze, every other character starting with the leftmost wall is also a lattice point.

```
                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  D|  D E|G E F|  F  |  G  |    |  D|  D E|G E F|  F  |  G  |
                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            Figure 4                         Figure 5

```

The rules for navigating this maze are as follows. Every move can be represented as either forward (`>`) or backward (`<`). Forward and backward here by default have the same meaning as our intuitive spatial awareness; forward goes to the position immediately to the right, and backwards immediately to the left.

Warp points represent locations that asymmetrically swap connectedness with neighbors. If you're coming from a neighbor to a warp point, the position of the two warp points is swapped; if you're coming from a warp point to a neighbor, they are not swapped. For example, in Figure 6, moving backwards from 1 brings you to 2 (since 1 is the neighbor of G, and we're moving from the neighbor, points 2 and @ are swapped). Moving forward from 2 (warp point G) brings you to 3 (here, we're starting from a warp point, so there's no swap). Likewise, moving backwards from 3 brings you to @.

```
        54 2367    89^   @1
|  D|  D E|G E F|  F  |  G  |
                     Y     X
          Figure 6

```

Figure 6 also shows an example navigation from X to Y, using the sequence of moves `<<>><>>>>>`. These moves bring you to the points labeled `123456789^` respectively, in that order. Feel free to explore it yourself using the code snippet in the next section.

## Converting 2D to 1D

Given a 1D maze, one can create a graph where each node is either a dead end or a warp point pair, and edges exist between any two nodes connected along a corridor. This graph allows us to compare 1D and 2D mazes.

For example, the 1D maze in Figure 4 is the same maze in Figure 1. To see why, Figure 7 adds labels to dead ends. Using those labels to build a graph, Figure 7's graph is simply Figure 3 again. Figure 8 shows a breakout of building this graph.

```
|  D|  D E|G E F|  F  |  G  |
 A   C           B   J H   I
          Figure 7

|  D|  D E|G E F|  F  |  G  |
+ + + + + + + + + + + + + + + <- lattice points
|A  |C    |     |B   J|H   I| <- dead ends
|A D|C D E|G E F|B F J|H G I| <- all nodes (dead ends+warp points); i.e.:
                                 "where each end is either a dead end
                                  or a warp point pair"; note that each
                                  pair of warp points is the same node.
|A-D|C-D-E|G-E-F|B-F-J|H-G-I| <- corridors; note each is a connection, since
  1   2 3   4 5   6 7   8 9      "edges exist between any two nodes
                                  connected along a corridor"
   graph {                 graph {
     A -- D  // 1 <---->     A -- D
     C -- D  // 2 <---->     C -- D
     D -- E  // 3 <---->     D -- E
     G -- E  // 4 <---->     E -- G
     E -- F  // 5 <---->     E -- F
     B -- F  // 6 <---->     B -- F
     F -- J  // 7 <---->     F -- J
     H -- G  // 8 <---->     G -- H
     G -- I  // 9 <---->     G -- I
   }                ^      }
    Built from      |      From Figure 3
     1D maze         `-> isomorphic mappings
                Figure 8

```

(Note that the labels and layout of each graph were artificially chosen to align for illustration purposes; generally speaking this is a graph isomorphism problem).

The following snippet is provided to help visualize the mechanics of the 1D maze and the connection between the 1D maze, the equivalence graph, and the 2D maze.

```
var mazeloc = 27; var cheese=21; var pnode=9; var cnode=9;
var spacing = "                            ";
function newCheese() {
   while(cheese==mazeloc){
      var rnum=Math.ceil(Math.random()*23);
      if(rnum>3) ++rnum; if(rnum>9) ++rnum; if(rnum>15)++rnum; if(rnum>21)++rnum;
      cheese=rnum;
   }
   document.getElementById("cheese").innerHTML = spacing.substr(1,cheese)+"#";
}
function getNodeClass(node) {
  switch (node) { case 1: return "ANode"; case 2: return "BNode"; case 3: return "CNode";
      case 4: return "DNode"; case 5: return "ENode"; case 6: return "FNode";
      case 7: return "GNode"; case 8: return "HNode"; case 9: return "INode"; case 10: return "JNode"; } }
function getNodeDefCol(node) {
  switch (node) { case 1: case 2: case 3: case 8: case 9: return "#666"; default: return "#000"; } }
function markMove() {
  var newNode = nodeByLocation(mazeloc);
  if (newNode==0) return;
  var pn = document.getElementsByClassName(getNodeClass(pnode));
  for (var i=0; i<pn.length; ++i) { pn[i].style.color = getNodeDefCol(i); pn[i].style.backgroundColor = "#FFF"; pn[i].style.fontWeight = "400";}
  var cn = document.getElementsByClassName(getNodeClass(cnode));
  for (var i=0; i<cn.length; ++i) { cn[i].style.color = "#800"; cn[i].style.backgroundColor = "#ED9"; cn[i].style.fontWeight="700"; }
  var nn = document.getElementsByClassName(getNodeClass(newNode));
  for (var i=0; i<nn.length; ++i) { nn[i].style.color = "#F00"; nn[i].style.backgroundColor = "#FE8"; nn[i].style.fontWeight="700"; }
  pnode=cnode; cnode=newNode;
}
function nodeByLocation(loc) { switch(loc) { default: return 0;
  case 1: return 1; case 17: return 2; case 5: return 3; case 3: case 7: return 4;
  case 9: case 13: return 5; case 15: case 19: return 6; case 11: case 25: return 7;
  case 23: return 8; case 27: return 9; case 21: return 10; } }
function onClickLeft() {
   switch (mazeloc) {
   case 1: case 5: case 11: case 17: case 23: break;
   case 8: mazeloc=3; break; case 12: mazeloc=25; break;
   case 14: mazeloc=9; break; case 20: mazeloc=15; break;
   case 26: mazeloc=11; break; default: mazeloc=mazeloc-1; break;
   }
   if(mazeloc==cheese) newCheese();
   markMove();
   document.getElementById("inmaze").innerHTML = spacing.substr(1,mazeloc)+"@";
}
function onClickRight() {
   switch (mazeloc) {
   case 3: case 9: case 15: case 21: case 27: break;
   case 2: mazeloc=7; break; case 6: mazeloc=3; break;
   case 8: mazeloc=13; break; case 12: mazeloc=9; break;
   case 14: mazeloc=19; break; case 18: mazeloc=15; break;
   case 24: mazeloc=11; break; default: mazeloc=mazeloc+1;
   }
   if(mazeloc==cheese) newCheese();
   markMove();
   document.getElementById("inmaze").innerHTML = spacing.substr(1,mazeloc)+"@";
}
```

```
<div><div style="float:left">
<pre><div id="cheese" style="color:#FA0; font-weight:bold">                     #</div>|<font class='ANode' color='#666'>A</font> <font class='DNode'>D</font>|<font class='CNode' color='#666'>C</font> <font class='DNode'>D</font> <font class='ENode'>E</font>|<font class='GNode'>G</font> <font class='ENode'>E</font> <font class='FNode'>F</font>|<font class='BNode' color='#666'>B</font> <font class='FNode'>F</font> <font class='JNode' color='#666'>J</font>|<font class='HNode' color='#666'>H</font> <font class='GNode'>G</font> <font class='INode' color='#666'>I</font>|
<div id="inmaze" style="color:#00F;  background-color:#FFD">                           @</div><div id="dbg"></div></pre>
<div style="float:left"><button type="button" onclick="onClickLeft()"><</button></div>
<div style="float:right"><button type="button" onclick="onClickRight()">></button></div></div>
<div style="float:left">
<pre>  <font class='ANode' color='#666'>A</font>         <font class='BNode' color='#666'>B</font>
   \        |
    \       |
     \      |
  <font class='CNode' color='#666'>C</font>---<font class='DNode'>D</font>-<font class='ENode'>E</font>---<font class='FNode'>F</font>
        |   |
    .---<font class='GNode'>G</font>   |
  .'   /    |
  <font class='HNode' color='#666'>H</font> <font class='INode' color='#666'>I</font>-'     <font class='JNode' color='#666'>J</font></pre>
</div>
<div style="float:left">
<pre>  +-+-+-+-+-+-+
  |<font class='ANode' color='#666'>A</font>|   |    <font class='BNode' color='#666'>B</font>|
  + + + + +-+-+
  |   | |     |
  +-+-+ +-+-+ +
  |<font class='CNode' color='#666'>C</font>   <font class='DNode'>D</font> <font class='ENode'>E</font>   <font class='FNode'>F</font>|
  +-+-+-+ +-+ +
  |      <font class='GNode'>G</font>  | |
  + +-+-+-+ + +
  |<font class='HNode' color='#666'>H</font>|<font class='INode' color='#666'>I</font>      |<font class='JNode' color='#666'>J</font>|
  +-+-+-+-+-+-+</pre>
</div></div>
```

As you navigate the 1D maze in this snippet, the last two nodes you touch are highlighted. The same nodes are highlighted the same way on the equivalence graph and the 2D maze.

---

In general, for any traditional 2D maze an equivalent 1D maze of this type can be created. A slightly more complex example is Figure 9:

```
+-+-+-+-+-+-+   +-+-+-+-+-+-+                   graph {
| |   |   | |   |A|   |   |B|   A         B       A -- D
+ + + + + + +   + + + + + + +    \       /        C -- D
|   | | |   |   |   | | |   |     \     /         D -- E
+-+-+ + +-+-+   +-+-+ + +-+-+      \   /          B -- E
|           |   |C   D E    |   C---D-E           E -- F
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |\          E -- I
|         | |   |      F  | |     .---F \         F -- G
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /   \        G -- H
| |       | |   |G|H      |I|   G H-'     I       H -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)       } // (graphviz dot)
   Figure 9       Figure 10             Figure 11

|  D|  D E  |F E  |  F  |       |  D|  D E  |F E  |  F  |
                                 A   C     I     B G   H
      Figure 12                       Figure 13

```

This maze has a node with four paths (E in Figure 10). Figure 11 shows its graph. Figure 12 is an equivalent 1D maze; and Figure 13 shows the same maze with labels for dead ends to compare with Figure 11.

# Challenge

Given a 2D Maze as input, write a function or program that transforms the 2D maze into a 1D maze with warp points. Warp points may use any of the 52 letters in each case.

Input guarantees (if any of these aren't met in the input you don't have to deal with it):

* The input maze is connected (that is, you can always go from any spot to any other).
* The input maze is closed.
* The input maze is rectangular.
* All lattice points use `+`.
* All walls between lattice points on the same row use `|`
* All walls between lattice points in the same column use `-`.
* All spaces are part of a path (and all inside the maze).
* Paths are all spaces (this will always be traditional, non-warping)
* Paths are exactly one space wide.
* The maze is built by connecting points on a lattice.
* There are no more than 52 total nodes (i.e., dead ends plus decision points) in the maze's graph.

Output format:

1. Your output should be **a single line** showing a 1D maze.
2. Your output should have no leading/trailing whitespace; except that a trailing newline is fine.
3. The first character and every other character afterwards are lattice points.
4. All walls should be on lattice points; and all warp points between them.
5. The graph of your 1D maze should be equivalent to the graph of the 2D maze.
6. Your 1D mazes must be compact; all non-lattice points must be dead ends (i.e., adjacent to walls) or warp points.
7. The **only letters** in your output should be warp points. Each warp point occurs on the line exactly twice.

Example:

```
|  D|  D E|G E F|  F  |  G  | <- (1,2) The single line output
+ + + + + + + + + + + + + + + <- lattice point spacing... (3)
                                 (4,6) lattice points are all walls or spaces
                                 (5) See Figure 8
                                 (7) D, E, F, G appear twice; no other labels

```

This is code-golf. The winner is the correct non-loophole submission with the least bytes.

# Testing

There are no test cases for this challenge, since there are a large number of correct outputs for any nontrivial maze.

I have, however, built a checker in C++ (this checker graphs both solutions through a graph canonicalization).

In addition, here are a few examples to help illustrate proper formatting:

*Example 1*

```
+-+-+-+-+-+-+
| |   |     |
+ + + + +-+-+
|   | |     |
+-+-+ +-+-+ +
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E|G E F|  F  |  G  |

```

*Example 2*

```
+-+-+-+-+-+-+
| |   |   | |
+ + + + + + +
|   | | |   |
+-+-+ + +-+-+
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E  |F E  |  F  |

```

More examples can be found in here.

# Answer
# Python 2 with igraph, ~~492~~ 369 bytes

```
import igraph,string
def f(s):
 C=s.find('\n')/2;N=' ';g=igraph.Graph(0,[(i,i+j)for i in range(len(s)/(4*C+4)*C)for j in(1,C)if s[(i/C*2+1)*(2*C+2)+i%C*2+2*j+j/C*3]==N]);V=g.vs;g.d=g.degree;O='';V(_d=1)[N]=N;V(_d_gt=2)[N]=list(string.ascii_letters)
 while g.es:
    v=V(_d=1)[0];O+='|'+v[N]
    while g.d(v):w=v.neighbors()[0];g-=(v,w);v=w;O+=N+v[N]if v[N]else''
 print O+'|'

```

(The fifth and sixth lines each begin with a tab, not four spaces as StackExchange shows.)

* Saved six bytes rearranging some arithmetic
* Saved seven bytes using a slice instead of zip
* Saved three bytes using `g+=tuple(v.neighbors())` instead of `g.add_edge(*v.neighbors())`
* Saved seven bytes using `g-=g.es[g.incident(v)]` instead of `g.delete_edges(g.incident(v))`
* Saved eleven bytes aliasing `g.d=g.degree`
* Saved 52 bytes (!) eliminating a loop which contracted all the corridors by replacing degree-2 vertices with an edge between their neighbors. Instead, the output loop just ignores these vertices.
* Saved 13 bytes noticing that when assigning names, igraph doesn't care if the provided iterable is too long
* Saved four bytes by not having a variable `R` for the number of rows, moving its calculation to the only use point
* Saved two bytes changing the second-level indentation to tabs instead of spaces
* Saved six bytes rearranging `2*(i%C)` to `i%C*2`, `2*(i/C)` to `i/C*2`, and `(C-1)*j` to `j*C-j`
* Saved four bytes naming `N='n'`
* Saved one byte determining if a character is space using `<'-'` rather than `==' '`, under the assumption that only valid characters appear.
* Then realized I can name the vertex attribute `' '` instead of `'n'`, and reuse `N` for the two literal spaces in the source, and `==N` instead of `<'-'`, saving five more bytes

A somewhat ungolfed version follows. The basic idea is to first make a graph on all the maze vertices (the spots with odd row and column when zero-indexed.) There is an edge from one vertex to the next one on the same row if the following character is a space, and not `|`. There is an edge from the vertex to the one right below it if the corresponding character in the following row is a space, and not `-`.

After building this graph, we pick any leaf, and follow along successively adjacent vertices, writing out their names if they are not a corridor, and deleting used edges, till we get stuck. Then we take another leaf and continue till all the edges are gone.

```
import string
import igraph
def f(s):
  C = s.find('\n')/2 # number of maze vertices in each row
  R = len(s)/(4*C+4) # number of rows
  def strpos(r, c):
    """Index of the vertex at row r, col c in the newline-delimited string s"""
    return (2*r+1)*(2*C+2) + 2*c + 1
  def vertpos(i):
    """Index of the i-th vertex in s"""
    return strpos(i/C, i%C)
  g = igraph.Graph(edges=[(i, i+(C if j else 1))
                          for i in range(R*C)
                          for j in (0, 1)
                          if s[vertpos(i)+(2*C+2 if j else 1)] == ' '])
  V = g.vs # the graph's vertex sequence
  O = ''
  V(_degree=1)['n'] = ' ' # All leaves are named space
  W = V(_degree_gt=2) # All warp points...
  W['n'] = list(string.ascii_letters[:len(W)]) # ...are named successive letters
  while g.es: # while any edges remain...
    v = V(_degree=1)[0] # find a leaf
    O += '|'+v['n'] # start a new 'block'
    while v.degree():
      w = v.neighbors()[0] # pick a neighbor
      g -= (v, w) # delete that edge
      v = w
      if v['n']: # If it's a dead end or warp point...
        O += ' '+v['n'] # ...write out the new neighbor
  print O+'|'

```

You can see results for the five example mazes. (Unfortunately, `igraph` is not available on Try It Online; these results were exported from SageMathCloud.)
> 3 votes

# Answer
# Haskell - ~~481~~ ~~405~~ 387 bytes

```
import Data.List
s&t=elemIndices s t
l=last
c!(x:y:z)=l$(y:c)!(x:z):do{[x:p,q]<-mapM([id,reverse]<*>)[[x],[y]];x&[l q];[[]!((q++p):c++z)]}
c![x]=x:[]!c
c!z=z
main=interact(\m->let{g=' '&m;
u=(\\[k|k<-g,length(v>>=(k&))==2])<$>[]!v;
v=[[x,y]|x<-g,y<-g,elem(y-x-1)[0,head$'\n'&m]];
}in '|':(u>>=(++"|").init.(>>=(:" ").toEnum.((+)<*>(+65).(*32).(`div`26)).l.(-1:).(&(nub$u>>=init.tail)))))

```

This creates a list of spaces that are in the maze, numbered by index in the string, and uses it to find all the pairs of adjacent spaces. It then stitches the pairs together into longer sequences of points based on matching first/last elements and removes the corridors, so that each sequence is one room in the 1D maze. The sequences are then translated into a string by replacing points on the interior of at least one room (the warp points) into corresponding letters and the rest into spaces.

The 2D maze is read from STDIN and the 1D maze is printed to STDOUT.

Edit: Reduced by 62 bytes rearranging a bunch of stuff and modifying the algorithm a bit, and another 14 by replacing `chr` with `toEnum` as suggested by Laikoni.

Edit 2: Saved 13 more bytes by simplifying the logic in `(!)`, 3 by using the list pattern match sugar, and 2 by using `>>=` to concat in `u`.
> 4 votes

---
Tags: code-golf, graph-theory, maze
---


# Question
Title: Shortest representation of an Underload number
# Flavour text

The stack-based esolang Underload has some interesting ties to functional programming. One of them is its treatment of the numerical datatype—like the lambda calculus, you represent the natural number N by a function which perform an action N times.

To make things simple, we will only consider only the following subset of Underload commands:

* `:` \- This command duplicates the top item on the stack.
* `*` \- This command concatenates the top two items on the stack into a single item.

We define an *Underload numeral N* as a string of `:` and `*` which, when executed, consume the top item on the stack, and produce N copies of that item concatenated together. Some examples:

* There are no Underload numerals 0, -1, 1/2, π.
* The empty string  is the Underload numeral 1, because it leaves the stack untouched.
* `:*` is the Underload numeral 2, because it duplicates the top item, and then concatenates those two copies together into a single item: `(A):*` = `(A)(A)*` = `(AA)`.
* `::**` is the Underload numeral 3: `(A)::**` = `(A)(A):**` = `(A)(AA)*` = `(AAA)`.
* `:::***` is the Underload numeral 4.
* `:*:*` is also the Underload numeral 4: `(A):*:*` = `(AA):*` = `(AA)(AA)*` = `(AAAA)`.

In general, you will find that, if `M` and `N` are the Underload numerals M and N, then `:N*` is the numeral N+1, and `MN` is the numeral M×N.

# The challenge

Your task is to write the shortest program (taking input on STDIN) or function (taking input via argument) which produces the **shortest representation of the Underload numeral for its input** as a string. That is to say, if the input is a positive natural number N \> 1, you must produce an Underload numeral N whose length in characters is less than or equal to that of every other Underload numeral N.

Sample inputs and outputs: ("Input - `OUTPUT`.")

* 1 - .
* 2 - `:*`.
* 5 - `::*:**` (2×2+1).
* 7 - `::*::***` (2×3+1) or `:::**:**` (3×2+1).
* 33 - `::*:*:*:*:**` (2×2×2×2×2+1).
* 49 - `::*:*:*:*::***` (16×3+1, length 14) but not `::*::***::*::***` (7×7, length 16).

If the input is not a positive natural number, you are free to return an error, produce undefined behaviour, or even fail to terminate. An explanation of your submission's method of finding the answer is appreciated.

Standard loophole restrictions apply: no extra input, no web requests, output/return value must be exactly the answer and not an infinite random stream of `:` and `*`, etc.

# Answer
> 4 votes
## GolfScript (61 60 55 54 53 chars)

```
~:X'']({:A{.'.+'\*A{2$+}%~}%}*{,}${1\~X=}?{44/'*:'=}%

```

This is less tricky than my earlier version and takes a slightly different approach, but it's still brute force. We know that `':'X*'*'X*+` is a candidate solution, so if we generate all well-balanced strings up to that length and take the shortest one which evaluates to the right thing we can be certain to find one.

```
# Evaluate input and store the target number in X
~:X
# Seed the generator with the empty string
'']
# X times...
({
    # Store the array of strings so far into A
    :A
    # Generate A' by mapping each element
    {
        # Dup: this leaves an untouched copy of the current string
        .
        # Wrap the duplicate in .+
        '.+'\*
        # For each element in A, generate that element suffixed with the current string
        A{2$+}%~
    }%
}*
# Order by length
{,}$
# Find the first element which evaluates to X
{1\~X=}?
# tr .+ :*
{44/'*:'=}%

```

Thanks to Howard, from whose solution I've stolen a couple of 1-char tweaks.

# Answer
> 4 votes
# Python 2.7 - 87 84 92

```
u=lambda n:n>1and min([u(i)+u(n/i)for i in range(2,n)if n%i<1]+[':'+u(n-1)+'*'],key=len)or''

```

**Explanation:**
This is a pretty straightforward solution. It recursively tests all possible representations of n as either the product of two numbers or as `:(n-1)*`, and then finds the minimum length solution. range(2,n) is necessary so that the recursion has bounded depth, and n\<2 gives the base case.

**Notes:**
i and n/i are the two factors of n. The ... and ... or ... replacement for ... if ... else ... doesn't work because '' evaluates to false. min of strings gives one of the shortest strings. Python 2.7 saves 1 character by using / instead of //.

Edit: Moved the base case to the back of the expression, allowing me to use ... and ... or ... and shave a couple spaces.

**Test cases:**

```
u(1)
''
u(5)
'::*:**'
u(49)
'::*:*:*:*::***'

```

# Answer
> 4 votes
## GolfScript (54 53 chars)

This is an approach which is in the spirit of Howard's (build strings which evaluate to the correct value and select the shortest, rather than brute force through candidate strings to find those which evaluate to the correct value), but is sufficiently different that I think it belongs in a separate answer.

```
~.''':*':s@,{):x,2>{:^~$x^/~$+{s\*}x^%*}%{,}$0=}/]((=

```

Online demo not available because it runs a buggy version of the interpreter.

```
# Let <N> denote the string which evaluates to N
# We want to enter the main loop with three values on the stack: <0> <1> <2>
# However, we'll never use <0>, so we can actually replace that with any value at all.
# Getting the input from underneath 3 items would normally use two stack manipulations.
# Trick: let's use the input value for <0>! (This gives a further bonus later).
# NB We store the value of <2> in the variable s
~.''':*':s@
# for x=1 to input_value ...
,{):x
    # for ^=2 to x-1 ...
    ,2>{:^
        # Use negative stack offsets to index the stack from the start
        # I.e. -1$ gets the first item on the stack, which is <0>
        # -2$ gets the second item on the stack, which is <1>
        # In general, val~$ gets <val>
        ~$x^/~$+
        # We have the string <^><x / ^> on the stack.
        # Increment it (x % ^) times to get a candidate <x>.
        {s\*}x^%*
    }%
    # Select a shortest string.
    {,}$0=
}/
# Group the stack into one array and select the appropriate offset,
# reusing that hacky <0> substitute for the offset.
]((=

```

# Answer
> 3 votes
### GolfScript, 63 58 56 characters

```
~n./\{:v~[':*'1$*v,,2>{v,\%!},{.v=v,@/v=+}/]{,}$0=]}*-2=

```

The code takes input on STDIN and prints the result.

Examples:

```
> 49
:::**:*:*:*:**

> 1234
::::*:*:*:**:*:*:**::**::***

```

You can test your own cases online.

# Answer
> 2 votes
# Brachylog 2, 30 (maybe eventually 26) bytes, language postdates challenge

Here's a function which works with the current Brachylog 2 implementation (and returns a list of character codes because the current implementation is having some issues with string handling):

```
∧.l∧?{ḋp~c×ᵐ{-₁↰₁:[42,58]c↻}ᵐc}

```

Try it online!

The language is still very new. Here's a **26 byte** version of the program that should work according to the specification, but uses some unimplemented features, and thus isn't valid yet, but maybe will be in future (it's also even less efficient):

```
{ḋp~c×ᵐ{-₁↰₁:"*:"c↻}ᵐc}ᶠlᵒh

```

## Explanation

```
∧.l∧?{ḋp~c×ᵐ{-₁↰₁:[42,58]c↻}ᵐc}
∧.l∧?                            Evaluation hint: try shortest outputs first
     {                        }  Define an inner function
      ḋ                          Prime factor decomposition of the input
       p                         Find a permutation
        ~c                       Find an inverse concatenation (i.e. partition)
          ×ᵐ                     Take the product of each set inside the partition
      ḋp~c×ᵐ                     Find a decomposition into factors ≥ 2
            {              }ᵐ    For each of those factors:
             -₁                  Decrement it
               ↰₁                Call the inner function recursively
                 :[42,58]c       Append "*:" (as character codes)
                          ↻      Move the last element to the start
                             c   Append the results together

```

The basic idea is fairly simple: we alternate between decomposing the number into (1 or more) factors (not necessarily prime factors, but factors of 1 are not allowed), and expressing each of those as 1 + (a representation obtained from a recursive call). This is guaranteed to search all possible Underload representations of the number (we can apply a multiplication stage "twice in a row" by multiplying together more than 2 numbers, and an increment stage twice in a row via separating them with a multiplication stage that multiplies together just one number). We don't need an explicit base case, because decomposing 1 into prime factors gives us an empty list, and thus we construct it with a multiplication stage that multiplies zero numbers together.

The program is fairly inefficient, especially because the evaluation order hint I gave (generate answers shortest to longest in terms of the size of the eventual output), while solving the "shortest" part of the question, isn't that great in terms of actually making the program complete quickly (a much more *useful* hint would be "generate only the shortest answer at each recursive stage", but that takes more bytes…). Additionally, `ḋp~c×ᵐ` can generate multiplicative partitions several times each, making the program do a lot of redundant work.

# Answer
> 0 votes
# J - 81 char

For posterity, this was the best that I could do in J.

```
_2{::(0&(][,0{<@;"1@({~#(#~]-:"1<.)@(],.%)2}.i.@#)(/:#&>)@,':'<@,'*',~>@{:),~)&a:

```

We create a list of results, beginning with two empty strings (that's the `,~` and `a:`) representing 0 (never used) and 1, and then iterate a verb over them (sneaky use of hooks, trains and `&`) that appends the next number's shortest representation.

The actual verb that we iterate uses the length of the list as an indicator of what number we are operating on. First, we factor this number into pairs of factors (`#(#~]-:"1<.)@(],.%)2}.i.@#`), and retrieve each pair by pulling from the array (`{~`). We turn each of those pairs (there could be 0 of them if the number is prime) into single strings (`<@;"1`).

Then we append to that list the entry for the previous result bracketed by `:` and `*`, and sort this list by length (`(/:#&>)`). Finally, we take the first result from this list (`0{`) and append that to the end of the base array (`[,`). When the loop is done iterating, we have a list of length 2 more than the input, starting at 0. So what we have to return is the next-to-last string (`_2{::`).

```
   un =: _2{::(0&(][,0{<@;"1@({~#(#~]-:"1<.)@(],.%)2}.i.@#)(/:#&>)@,':'<@,'*',~>@{:),~)&a:
   un 49
::*:*:*:*::***
   un 1234
:*::*:*:*::*::***::*::*:****
   un 10010
:*::*:*::***::*:*:*:*:*:*:*::***
   2 * (1 + 3 * 2^2) * (1 + 3 * 2^7)
10010
   6!:2 'un 10010'   NB. time in seconds
19.5539

```

# Answer
> 0 votes
# Jelly, 33 bytes, language postdates challenge

```
ÆḌḊµ⁹÷Ñ;Ñð€
’ß”:;;”*W;ÇLÞḢµ“”>1$?

```

Try it online!

A straightforward brute force solution.

## Explanation

### Main program

```
’ß”:;;”*W;ÇLÞḢµ“”>1$?
              µ  >1$?  If input is greater than 1, then:
’ß                       Run recursively on the input - 1
  ”:;                    Prepend a colon
     ;”*                 Append an asterisk
        W;               Cons to:
          Ç                the result of the helper, on {the original input}
           LÞ            Sort by length
             Ḣ           Take the first (i.e. shortest) result
               “”      Otherwise, return an empty string

```

The main program uses the helper function to enumerate all possible ways to produce the value via multiplication, then tries producing the value by addition, and returns the shortest possibility. It also handles the base case (an input of `1`).

### Helper function

```
ÆḌḊµ⁹÷Ñ;Ñð€
ÆḌ µ     ð€            For all proper factors of the input
  Ḋ                    except the first (i.e. 1):
    ⁹÷                   Divide it into the input;
      Ñ                  Run the main program on it;
       ;                 Append the result of:
        Ñ                  the main program run on {the factor}

```

The helper function tries all possible methods of expressing the input as a multiplication of two numbers, and mutual-recursively calls the main program in order to get at their shortest representations.

# Answer
> 0 votes
# GNU Prolog, 96 bytes

```
v(N)-->{N#=1};{N#=A*B,A#<B,B#<N},v(A),v(B);{N#=M+1},":",v(M),"*".
s(N,S):-length(S,_),v(N,S,[]).

```

The first line is a grammar that implements Underload evaluation, and works in the reverse direction (actually, it doesn't quite work in the forward direction due to the `A#<B` constraint; change this to `A#<N` for a slower program that works both ways round). The second line defines the function-like predicate `s` (which is the function that's implemented as a solution to this program) which finds the shortest possible string which evaluates to the number given as input (this is frustratingly verbose for what's a relatively simple task, but that's Prolog for you…).

The program should be pretty self-explanatory, given that it's more or less a direct translation of the specification to a grammar, and then to Prolog syntax; the definition of `v` says that `N` is 1 in an empty string, or `N` is `A` × `B` (with `A` less than `B` less than `N`) and the string is the concatenation of `v(A)` and `v(B)`, or `N` is `M` \+ 1 and the string is `:` concatenated with `v(M)` concatenated with `*`. The second line is a bit subtler; `length(S,_)` means "S has some length", but specifying this as the first thing on the line acts as a hint to the Prolog implementation that it should check the shortest lengths first (which means we'll get the shortest possible length for a return value).

---
Tags: code-golf, number, stack
---


# Question
Title: Express a number - a modern "Des Chiffres et des Lettres"
# Express a number

Back in the 60s, the French invented the TV game show "Des Chiffres et des Lettres" (Digits & Letters). The goal of the Digits-part of the show was to come as close as you can to a certain 3-digit target number, using some semi-randomly selected numbers. The contestants could use the following operators:

* concatenation (1 and 2 is 12)
* addition (1 + 2 is 3)
* subtraction (5 - 3 = 2)
* division (8 / 2 = 4); division is only allowed if the result is a natural number
* multiplication (2 * 3 = 6)
* parentheses, to override the regular precedence of operations: 2 * ( 3 + 4 ) = 14

Each given number can only be used once or not at all.

For example, the target number 728 can be matched exactly with the numbers: 6, 10, 25, 75, 5 and 50 with the following expression:

```
75 * 10 - ( ( 6 + 5 ) * ( 50 / 25 ) ) = 750 - ( 11 * 2 ) = 750 - 22 = 728

```

In this code challenge, your are given the task to find an expression as close as possible to a certain target number. Since we're living in the 21st century, we'll introduce bigger target numbers and more numbers to work with than back in the 60s.

## Rules

* Allowed operators: concatenation, +, -, /, \*, ( and )
* The concatenation operator has no symbol. Just concatenate the numbers.
* There is no "inverse concatenation". 69 is 69 and can't be split in a 6 and a 9.
* The target number is a positive integer and has a maximum of 18 digits.
* There are at least two numbers to work with and a maximum of 99 numbers. These numbers are also positive integers with a maximum of 18 digits.
* It is possible (actually quite probably) that the target number can't be expressed in terms of the numbers and the operators. The goal is to get as close as possible.
* The program should finish in a reasonable time (a few minutes on a modern desktop PC).
* Standard loopholes apply.
* Your program may **not** be optimized for the test set in the "scoring" section of this puzzle. I reserve the right to change the test set if I suspect anyone violating this rule.
* This is *not* a codegolf.

## Input

The input consists of an array of numbers that can be formatted in any convenient way. The first number is the target number. The rest of the numbers are the numbers you should work with to form the target number.

## Output

The requirements for the output are:

* It should be a string that consists of:
    + any subset of the input numbers (except the target number)
    + any number of operators
* I prefer the output to be single line without spaces, but if you must, you may add spaces and newlines as you see fit. They will be ignored in the controlling program.
* The output should be a valid mathematical expression.

## Examples

For readability, all these examples have an exact solution and each input number is used exactly once.

Input: `1515483, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1`
Output: `111*111*(111+11+1)`

Input: `153135, 1, 2, 3, 4, 5, 6, 7, 8, 9`
Output: `123*(456+789)`

Input: `8888888888, 9, 9, 9, 99, 99, 99, 999, 999, 999, 9999, 9999, 9999, 99999, 99999, 99999, 1`
Output: `9*99*999*9999-9999999-999999-99999-99999-99999-9999-999-9-1`

Input: `207901, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0`
Output: `1+2*(3+4)*(5+6)*(7+8)*90`

Input: `34943, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0` Output: `1+2*(3+4*(5+6*(7+8*90)))` But also valid output is: `34957-6-8`

## Scoring

The penalty score of a program is the sum of the relative errors of the expressions for the testset below.

For example if the target value is 125 and your expression gives 120, your penalty score is abs( 1 - 120/125 ) = 0,04.

The program with the **lowest** score (lowest total relative error) wins. If two programs finish equally, the first submission wins.

Finally, the testset (8 cases):

```
14142, 10, 11, 12, 13, 14, 15
48077691, 6, 9, 66, 69, 666, 669, 696, 699, 966, 969, 996, 999
333723173, 3, 3, 3, 33, 333, 3333, 33333, 333333, 3333333, 33333333, 333333333
589637567, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
8067171096, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199
78649377055, 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462, 506, 552, 600, 650, 702, 756, 812, 870, 930, 992
792787123866, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169
2423473942768, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 2000000, 5000000, 10000000, 20000000, 50000000

```

# Previous similar puzzles

After creating this puzzle and posting it on the sandbox, I noticed something similar (but not the same!) in two previous puzzles: here (no solutions) and here. This puzzle is somewhat different, because it introduces the concatenation operator, I don't seek and exact match and I like to see strategies for coming close to the solution without brute force. I think it is challenging.

# Answer
> 5 votes
# C++17, score .0086

This program has non-deterministic penalty score due to thread races, so I'm declaring based on an average of three runs, each of which handled the test suite in under a minute:

```
score 0.000071 for 14(11*13) = 14143
score 0.000019 for (696699+66)*69 = 48076785
score 0.000069 for 333333+333333333+33333 = 333699999
score 0.000975 for 5(1((((555555255-1-1-4-5-5-5-5-4-4-4-4-4-4-4-4-4-4-4-4-4-5-3-3-3-3-3-3-3-3-3-3-3-3-3-5)/2*3/2-2)/2*3+2+1+1+1+1-1-1)/2*2/2/2/2)/2) = 589062470
score 0.000462 for (((199181197*41-193-191-179-173-167-163-157-151-149-139-137-131-127-113-109-107-103-101-97-89-83-79-73-71-67-61-59-53-47-43-17-3)/5*7+23)/2/11*13+19)/31*37 = 8063447296
score 0.000118 for (992930870*72+812+756+702+650+600+552+506+462+420+380+342-42-56-182-12-210-156-90-20-272-30-6-306)/240*132*2 = 78640130184
score 0.000512 for (((317811*832040*3-39088169-24157817-14930352-9227465-5702887-2178309-1346269-3524578-514229-196418-121393-17711-233-75025-46368-89-28657-4181-10946-6765-34-987-2584-13-610-8-1)/2-377-144)/5-1597)1 = 793193194211
score 0.005725 for 2(20((120000000*20000+50000000+10000000+5000000+2000000+100000+50000+10000+5000+2000-500-1000)/50)/5)+200+100+10 = 2409600268972
total score = .007951

real    0m57.876s
user    4m24.396s
sys     0m0.684s

score 0.000071 for 14(11*13) = 14143
score 0.000019 for (696699+66)*69 = 48076785
score 0.000069 for 333333+333333333+33333 = 333699999
score 0.001675 for (3((((((((555555455+5+5+5+5-1-1-4-4-4-4-4-4-4-4-4-1-4-4-4-4-5-3-3-3-3-3-4)/2*3/2-1)*2+5)/3*3+3)/2-3-3)/2*3/2*2+2)/2*2/2*3+2+1)/5/2)-1-1-1-1-1-1-1-1-1-2)/2*3 = 590624943
score 0.000973 for ((199181197*41-193-191-179-173-167-163-157-151-149-139-137-131-127-113-107-101-59-97-79-3-71-67-83-2-47-37-73-89-103-19-11-29)/5*7+109-23)/61*43 = 8059325224
score 0.000118 for ((992930870*72+812+756+702+650+600+552+506+462+420+380+342+306+272+240+210+182-0-56-110-20-90)/2-42-156)/30*132/12*6 = 78640132296
score 0.000512 for (((317811*832040*3-39088169-24157817-14930352-9227465-5702887-3524578-514229-196418-2178309-1346269-121393-75025-28657-10946-233-46368-89-17711-2584-6765-610-4181-34-987-55-1)/2-8-144-377)/5-1597)1 = 793193194161
score 0.004734 for 2(20((120000000*20000+50000000+10000000+5000000+2000000+100000+50000+10000+5000+2000-100-1000-500)/200*50/10)/5) = 2412000335827
total score = .008171

real    0m45.636s
user    3m30.272s
sys     0m0.720s

score 0.000071 for 14(11*13) = 14143
score 0.000019 for (696699+66)*69 = 48076785
score 0.000069 for 333333+333333333+33333 = 333699999
score 0.002963 for 1(((((((555555555+5+5+5+5+5+5+4+4+4+4-1-2-4-4-4-4-4-4-4-4-4-4-4-3-3-3-3)/2*3+3+2)/2*2+3+3)/2*2/2/2*3+3)/2-3-3)*3/2-1-3)/2*3/2/2)/2 = 587890622
score 0.000069 for ((((199181197*41-193-191-179-173-167-163-157-151-149-139-137-131-127-113-109-107-103-101-97-89-83-79-73-71-67-61-59-53-47-43-37-11)/7)2+3)/23*17-13-5)/31*29 = 8066615553
score 0.000118 for ((992930870*72+812+756+702+650+600+552+506+462+420+380-0-6-90-56-42-272-182-110-210-342-30-306)*2+12)/240*132 = 78640129524
score 0.000512 for (((317811*832040*3-39088169-24157817-14930352-9227465-5702887-2178309-1346269-3524578-514229-196418-121393-75025-46368-28657-144-55-17711-2584-10946-4181-6765-21-610-987-377-8-1)/2-89-13)/5-233-1597)1 = 793193192491
score 0.005725 for 2(20((120000000*20000+50000000+10000000+5000000+2000000+100000+50000+10000+5000+2000-500-1000)/50)/5)+200+100+10 = 2409600268972
total score = .009546

real    0m57.289s
user    4m19.488s
sys     0m0.708s

```

Here's the program; explanation is provided in comments. You can define `CONCAT_NONE` for traditional Countdown rules that don't permit concatenation, or `CONCAT_DIGITS` to allow concatenation of the input values, but not of any intermediate results. By default, without either defined, the most liberal rules are used.

```
#include <omp.h>

#include <algorithm>
#include <cmath>
#include <memory>
#include <set>
#include <string>
#include <utility>
#include <vector>

// We apply some principles to help us arrive at a good enough solution
// in a reasonable time:

// 1. Ruthlessly prune duplicate expressions from the candidate
//    list.  If we've seen a+b, then there's no need to consider
//    b+a.  Similarly, having seen (a+b)+c, then (a+c)+b can be
//    discounted.
// 2. Detect duplicates by storing batches of part-processed results
//    in sets before sending to the next pass.
// 3. Sort our candidates so that those containing a term near to the
//    target are first in line for further processing.
// 4. Gradually widen our acceptance margin as we proceed.  This
//    allows us to terminate quickly without exhaustively searching
//    the full problem space.
// 5. Parallelize the generation of candidate solutions using OpenMP.

// Define precedence values for our operators, so that we can print
// with the minimum sufficient parentheses.  The values are grouped
// into tens so that add/10 == subtract/10 and mult/10 == divide/10 -
// the operators use that for avoiding duplicate expressions.
static const int PREC_ADD = 26;
static const int PREC_SUBTRACT = 24;
static const int PREC_MULT = 16;
static const int PREC_DIVIDE = 14;
static const int PREC_CONCAT = 2;
static const int PREC_LITERAL = 0;

static const int PREC_MAX = 1000;

class LiteralTerm;

struct Term
{
    long value;
    int precedence;

    Term(long value, int precedence)
        : value(value), precedence(precedence)
    {}
    Term(const Term&) = default;
    virtual ~Term() = default;

    virtual std::string to_string(int p = PREC_MAX) const = 0;
    virtual LiteralTerm as_literal() const = 0;

    long distance(long target) const { return std::abs(value - target); }

    // We sort large values first, in the hope that this will approach
    // the target faster.
    bool operator<(const Term& o) const { return value > o.value; }
};

// We have two kinds of Term: a LiteralTerm is a leaf node of the
// expression tree, and a BinaryTerm is an internal node.
struct Operator;

class LiteralTerm : public Term
{
    std::string s;
public:
    LiteralTerm(std::string s) : Term(std::stol(s), 0), s(s) {}
    LiteralTerm(std::string s, long value) : Term(value, 0), s(s) {}
    std::string to_string(int = PREC_MAX) const override { return s; }
    LiteralTerm as_literal() const override { return *this; }
};

struct BinaryTerm : public Term
{
    Operator const *op;

    std::shared_ptr<const Term> a;
    std::shared_ptr<const Term> b;

    BinaryTerm(long value, const Operator* op, std::shared_ptr<const Term> a, std::shared_ptr<const Term> b);
    BinaryTerm(const BinaryTerm&) = default;
    BinaryTerm& operator=(const BinaryTerm&) = default;

    std::string to_string(int p = PREC_MAX) const;

    LiteralTerm as_literal() const override { return { to_string(), value }; }
};

struct TermList {
    std::vector<std::shared_ptr<const Term>> terms;
    std::vector<long> values;
    long target_value;
    long badness;

    TermList(std::vector<std::shared_ptr<const Term>> terms, long target_value)
        : terms(std::move(terms)),
          values(),
          target_value(target_value),
          badness(min_badness(this->terms, target_value))
    {
        values.reserve(terms.size());
        std::transform(terms.begin(), terms.end(),
                       std::back_inserter(values), [](auto t) { return t->value; });
        // Literals that begin with "0" need to be distinct from (but
        // adjacent to) equivalent non-literals.  Append a negative
        // value for each term with leading zeros.  There's an edge
        // case involving multiple leading zeros, but we'll ignore
        // that.
        for (const auto& v: terms)
            if (v->precedence <= PREC_CONCAT && v->value > 0 && v->to_string()[0] == '0')
                values.push_back(-v->value);
    }

    // Sort according to the term that's nearest to the target.
    bool operator<(const TermList& o) const
    {
        return std::make_tuple(std::cref(badness),   std::cref(values))
            <  std::make_tuple(std::cref(o.badness), std::cref(o.values));
    }

private:
    static long min_badness(const std::vector<std::shared_ptr<const Term>>& t, long target_value)
    {
        auto less_bad = [target_value](const auto& a, const auto&b)
            { return a->distance(target_value) < b->distance(target_value); };
        auto const& e = *std::min_element(t.begin(), t.end(), less_bad);
        return std::abs(e->value - target_value);
    }
};

using Set = std::set<TermList>;

// Detect duplicate expressions.  This will discount "3+2-3", "8*5*2/3/5"
// and similar expressions that contain simple pairs of inverse operands.
static bool contains_value(const Term& t, int precedence, long value)
{
    auto *const b = dynamic_cast<const BinaryTerm*>(&t);
    if (t.precedence == precedence)
        return t.value == value
            || b && b->b->value < value
            || b && contains_value(*b->a, precedence, value)
            || b && contains_value(*b->b, precedence, value);
    if (t.precedence/10 == precedence/10)
        // Advance through the subtractions to inspect the additions
        // (or through the divides to inspect the multiplications).
        return b && contains_value(*b->a, precedence, value);
    return false;
}

// An Operator is a factory producing binary terms of a given type,
// and for printing those terms.  Here's the abstract base class.
struct Operator
{
    using TermPointer = std::shared_ptr<const Term>;
    using BinaryTermPointer = std::shared_ptr<const BinaryTerm>;

    int const precedence;
    std::string const joiner;

    virtual std::string to_string(const Term &a, const Term &b) const {
        return a.to_string(precedence) + joiner + b.to_string(precedence);
    }

    virtual BinaryTermPointer make_term(TermPointer a, TermPointer b) const {
        long r = evaluate(*a, *b);
        return r ? std::make_shared<BinaryTerm>(r, this, a, b) : BinaryTermPointer();
    }

    virtual ~Operator() = default;

protected:
    Operator(int precedence, std::string joiner) : precedence(precedence), joiner(joiner) {}

    virtual long evaluate(const Term& a, const Term& b) const = 0;
};

// Now we define a subclass for each permitted operator
struct AddOperator : Operator
{
    AddOperator() : Operator(PREC_ADD, "+") {}

    long evaluate(const Term& a, const Term& b) const override
    {
        const auto *d = dynamic_cast<const BinaryTerm*>(&a);
        long r;
        return b.precedence/10 != PREC_ADD/10
            && a.precedence != PREC_SUBTRACT
            && b.value > 0
            && ! (d && d->precedence == this->precedence && d->b->value < b.value)
            && !__builtin_add_overflow(a.value, b.value, &r)
            ? r : 0;
    }
};
struct SubtractOperator : Operator
{
    SubtractOperator() : Operator(PREC_SUBTRACT, "-") {}

    long evaluate(const Term& a, const Term& b) const override
    {
        return b.precedence < PREC_SUBTRACT
            && a.value > b.value
            && !contains_value(a, PREC_ADD, b.value)
            ? a.value - b.value : 0;
    }
};
struct MultiplyOperator : Operator
{
    MultiplyOperator() : Operator(PREC_MULT, "*") {}

    long evaluate(const Term& a, const Term& b) const override
    {
        const auto *d = dynamic_cast<const BinaryTerm*>(&a);
        long r;
        return b.precedence/10 != PREC_MULT/10
            && b.value > 1
            && (b.value > 2 || a.value > 2)
            && ! (d && d->precedence == this->precedence && d->b->value < b.value)
            && !__builtin_mul_overflow(a.value, b.value, &r)
            ? r : 0;
    }
};
struct DivideOperator : Operator
{
    DivideOperator() : Operator(PREC_DIVIDE, "/") {}

    long evaluate(const Term& a, const Term& b) const override
    {
        return b.precedence/10 != PREC_DIVIDE/10 && b.value > 1
            && a.value % b.value == 0
            && !contains_value(a, PREC_MULT, b.value)
            ? a.value / b.value : 0;
    }
};

struct ConcatOperator : Operator
{
    ConcatOperator() : Operator(PREC_CONCAT, "") {}

    long evaluate(const Term& a, const Term& b) const override
    {
#ifdef CONCAT_DIGITS
        if (a.precedence > PREC_CONCAT || a.value == 0 || b.precedence >= PREC_CONCAT)
            return 0;
#else  // CONCAT_FULL
        if (b.precedence == PREC_CONCAT || a.value == 0)
            return 0;
#endif
        long bv = b.value, av = a.value, x = 1, r;
        if (b.precedence > PREC_CONCAT) while (x <= bv) x*= 10;
        else { int d = b.to_string().length(); while (d--) x*= 10; }
        return __builtin_mul_overflow(av, x, &r) || __builtin_add_overflow(r, bv, &r) ? 0 : r;
    }
};
struct ReverseConcatOperator : ConcatOperator
{
    BinaryTermPointer make_term(TermPointer a, TermPointer b) const override
    {
        return ConcatOperator::make_term(b, a);
    }
};

static const std::vector<std::shared_ptr<const Operator>> ops{
#ifndef CONCAT_NONE
        std::make_shared<ConcatOperator>(),
        std::make_shared<ReverseConcatOperator>(),
#endif
        std::make_shared<MultiplyOperator>(),
        std::make_shared<AddOperator>(),
        std::make_shared<SubtractOperator>(),
        std::make_shared<DivideOperator>(),
};

// Implement the BinaryTerm members that use Operator
BinaryTerm::BinaryTerm(long value, const Operator* op, std::shared_ptr<const Term> a, std::shared_ptr<const Term> b)
    : Term(value, op->precedence), op(op), a(std::move(a)), b(std::move(b))
{}

std::string BinaryTerm::to_string(int p) const
{
    auto const s = op->to_string(*a, *b);
    return (p/10) < (precedence/10) ? "("+s+")" : s;
}

// An object to represent our target value, and how close we have
// reached so far.
struct Target
{
    const long value;
    double max_badness = 0;

    LiteralTerm best = {"0"};
    long best_badness = value;

    bool done() const { return best_badness < max_badness; }
    double score() const { return 1.*best_badness/value; }

    void update(const Term& t)
    {
        auto badness = std::abs(t.value - value);
        if (badness < best_badness) {
            best = t.as_literal();
            best_badness = badness;
        }
    }

    void update(const TermList& terms)
    {
        for (auto t: terms.terms)
            update(*t);
    }

    void increase_threshold(size_t items_seen)
    {
        // Adjust our acceptance threshold nearer to accepting 0 by
        // 0.01% for every million values seen.
        max_badness += (value - max_badness) * .0001 * std::exp(items_seen / 1000000);
    }
};

// OpenMP reduction for sets
auto merge(auto& a, auto& b)
{
    auto it = a.begin();
    for (auto&& e: b)
        it = a.insert(std::move(e)).first;
    return a;
}
#pragma omp declare reduction(merge: Set: merge<Set>(omp_out, omp_in) ) \
    initializer(omp_priv = Set())

// We run a cascade of pair-wise combination steps, where for each
// input TermList, we generate every possible allowed pairing of its
// terms, and pass that through (in batches) to the next stage.
struct Combiner
{
    std::unique_ptr<Combiner> const next;
    Target& target;
    size_t const max_output_size;
    size_t const nterms;

    Set input = {};
    size_t output_size = 0;

    Combiner(Target& target, size_t nterms, size_t max_output_size)
        : next(nterms > 0 ? std::make_unique<Combiner>(target, nterms-1, max_output_size) : nullptr),
          target(target),
          max_output_size(max_output_size),
          nterms(nterms)
    {}

    inline void insert(const TermList&& t)
    {
        target.update(t);
        if (target.done()) return;
        if (next) {
            if (input.insert(t).second)
                output_size += count_distinct_pairs(t);
            if (output_size >= max_output_size)
                process_input();
        }
    }

    void finish()
    {
        process_input();
        if (next)
            next->finish();
    }

private:
    // Here's where we do the real work - generating and sifting the
    // combined terms for the next pass.
    void process_input()
    {
        if (target.done()) {
            return;
        }

        if (!next)
            return;

        // Move the elements into a vector, so we can parallelize the
        // for-loop.
        auto in = std::vector<Set::value_type>();
        in.reserve(input.size());
        std::move(input.begin(), input.end(), std::back_inserter(in));
        input.clear();
        output_size = 0;

        auto out = Set();

#pragma omp parallel reduction(merge:out)
        {
#pragma omp for
            for (auto it = in.begin();  it < in.end();  ++it)
            {
                try {
                    const auto end = it->terms.cend();
                    for (auto i = it->terms.cbegin();  i != end;  i = std::upper_bound(i, end, *i))
                        for (auto j = i+1;  j != end;  j = std::upper_bound(j, end, *j)) {
                            for (const auto& op: ops) {
                                auto x = op->make_term(*i, *j);
                                if (x) out.insert(replace(*it, i, j, x));
                            }
                        }
                } catch (const std::bad_alloc&) {
                    // Ignore it; process what we've generated so far.
                }
            }
        }

        // Now we're in single-threaded code, we can pass the combined
        // results to the next combiner.
        for (auto& o: out)
            next->insert(std::move(o));

        target.increase_threshold(out.size());
    }

    // Helper methods used by the above

    // An upper bound on the possible number of output TermLists,
    // assuming every combination is valid.  If all n terms in the
    // input list are distinct, that's just ½n(n-1), but if values
    // are duplicated, we need to reduce n to the number of distinct
    // values, and then add in the cases where we pick two of the
    // same value.
    static int count_distinct_pairs(const TermList& terms)
    {
        int distinct = 0, duplicated = 0;
        auto it = terms.terms.begin(),
            end = terms.terms.end();
        while (it != end) {
            ++distinct;
            auto const& v = (*it)->value;
            if (++it == end || (*it)->value != v) continue;
            ++duplicated;
            while (++it != end && (*it)->value == v)
                ;
        }
        return distinct * (distinct - 1) / 2 + duplicated;
    }

    // Create a new TermList from o by replacing elements i and j with
    // newly-created term n.
    static TermList replace(const TermList& o, auto i, auto j, std::shared_ptr<const Term> n)
    {
        std::vector<std::shared_ptr<const Term>> r;
        r.reserve(o.terms.size() - 1);
        auto added = false;
        for (auto k = o.terms.begin();  k != o.terms.end();  ++k) {
            if (!added && (*k)->value < n->value) { r.push_back(n); added = true; }
            if (k != i && k != j) r.push_back(*k);
        }
        if (!added) r.push_back(n);
        return { r, o.target_value };
    }
};

#include <iostream>
std::ostream& operator<<(std::ostream& o, const Term& t)
{
    return o << t.to_string()<< " = " << t.value;
}
std::ostream& operator<<(std::ostream& o, const TermList& t)
{
    auto *sep = "";
    o << "[" << t.badness << "] ";
    for (auto const& x: t.terms)
        o << sep << *x, sep = ", ";
    return o;
}

int main(int argc, char **argv)
{
    if (argc < 3) {
        std::cerr << "Usage: " << argv[0] << " target term ...";
        return EXIT_FAILURE;
    }
    auto target = Target{std::stol(*++argv)};

    std::vector<std::shared_ptr<const Term>> terms;
    while (*++argv) {
        auto t = std::make_shared<LiteralTerm>(*argv);
        target.update(*t);
        terms.push_back(t);
    }
    std::sort(terms.begin(), terms.end());

    // Construct the sieve
    Combiner search{target, terms.size(), 2500000/terms.size() + 1}; // tunable - max set size
    search.insert({terms, target.value});
    search.finish();

    std::cout << "score " << std::fixed << target.score() << " for " << target.best << std::endl;
}

```

I compiled this using GCC 6.2, using `g++ -std=c++17 -fopenmp -march=native -O3` (along with some debugging and warning options).

# Answer
> 3 votes
# Python 2.7. Score: 1,67039106

So, I decided to have a throw at it myself. Nothing too fancy. This program sorts the numbers in reverse order (big to small), and tries all operators sequentially on the numbers. Blazing fast, but a performance that deserves to be superseded.

Here is the program:

```
import sys

def score(current,target):
    return abs(1.0-current/float(target))

# Process input and init variables
targetvalue=int(sys.argv[1].strip(','))
numbers=[int(a.strip(',')) for a in sys.argv[2:]]
numbers.sort(reverse=True)
expression='('+str(numbers[0])+')'
currentvalue=nextvalue=testvalue=numbers[0]

# Loop over all values (except the first one)
for value in numbers[1:]:
    # Set multiplication as the reference operator...
    testvalue=currentvalue*value
    minscore=score(testvalue,targetvalue)
    operator="*"
    nextvalue=testvalue

    # then try division (only if result is integer and not divided by zero)...
    if value!=0 and currentvalue%value==0:
        testvalue=currentvalue/value
        if score(testvalue,targetvalue)<minscore:
            operator="/"
            minscore=score(testvalue,targetvalue)
            nextvalue=testvalue

    # and addition...
    testvalue=currentvalue+value
    if score(testvalue,targetvalue)<minscore:
        operator="+"
        minscore=score(testvalue,targetvalue)
        nextvalue=testvalue

    # and subtraction...
    testvalue=currentvalue-value
    if score(testvalue,targetvalue)<minscore:
        operator="-"
        minscore=score(testvalue,targetvalue)
        nextvalue=testvalue

    # and concatenation
    testvalue=int(str(currentvalue)+str(value))
    if score(testvalue,targetvalue)<minscore:
        operator=""
        minscore=score(testvalue,targetvalue)
        nextvalue=testvalue

    # finally check if any operator improces the score. If so, append to the expression
    if score(nextvalue,targetvalue)<score(currentvalue,targetvalue):
        expression='('+expression+operator+str(value)+')'
        currentvalue=nextvalue

print(expression)

```

The output for all the test cases is:

```
((((((15)14)*13)-12)-11)-10)
((((((((((((999)996)+969)+966)+699)+696)+669)+666)*69)-66)-9)-6)
(((((((((333333333)+333333)+33333)+3333)+333)+33)+3)+3)+3)
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((5)5)5)5)5)5)5)5)5)+5)+5)+5)+5)+5)+5)+4)+4)+4)+4)+4)+4)+4)+4)+4)+4)+4)+4)+4)+4)+4)+3)+3)+3)+3)+3)+3)+3)+3)+3)+3)+3)+3)+3)+3)+3)+2)+2)+2)+2)+2)+2)+2)+2)+2)+2)+2)+2)+2)+2)+2)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)
((((((((((((((((((((((((((((((((((((((((((((((199)197)193)+191)+181)+179)+173)+167)+163)+157)+151)+149)+139)+137)+131)+127)+113)+109)+107)+103)+101)+97)+89)+83)*79)-73)-71)-67)-61)-59)-53)-47)-43)-41)-37)-31)-29)-23)-19)-17)-13)-11)-7)-5)-3)/2)
(((((((((((((((((((((((((((((((992)930)870)+812)+756)+702)+650)+600)+552)+506)+462)+420)+380)+342)+306)+272)+240)+210)+182)*156)-132)-110)-90)-72)-56)-42)-30)/20)*12)-6)-2)
((((((((((((((((((((((((((((((((((((((39088169)+24157817)+14930352)+9227465)+5702887)+3524578)+2178309)+1346269)+832040)+514229)+317811)+196418)+121393)+75025)+46368)+28657)+17711)*10946)-6765)-4181)-2584)-1597)-987)-610)-377)-233)-144)-89)-55)-34)-21)-13)-8)-5)-3)/2)+1)+1)
(((((((((((((((((((((50000000)+20000000)+10000000)+5000000)+2000000)+100000)*50000)-20000)-10000)-5000)-2000)-1000)-500)-200)-100)-50)-20)-10)/5)*2)+1)

```

---
Tags: code-challenge, arithmetic, expression-building
---


title: OOP: Overlapping Oriented Programming

text:
# Question
Title: OOP: Overlapping Oriented Programming
One of the lesser known programming paradigms which seems rather fitting for code golfing is *Overlapping Oriented Programming (OOP)* \*. When writing partly identical code, many bytes can be saved by simply overlapping the identical parts and remembering in some way where the two original code lines start. Your task is to write two **overlapping** programs or functions `compress` and `decompress` with the following specification:

<sup>\*Do not use in production code, probably.</sup>

## `compress`

`compress` takes two strings in any convenient format and overlaps them as much as possible. That is a string `s` with minimal length is returned such that both input strings are substrings of `s`. Additionally, some output which identifies the start and end indices of both string is returned.

**Examples:** (The exact IO-format is up to you)

```
compress("abcd", "deab") -> "deabcd" ((2,5),(0,3))
compress("abcd", "bc")   -> "abcd" ((0,3),(1,2))
compress("abc", "def")   -> "abcdef" ((0,2),(3,5)) or "defabc" ((3,5),(0,2))

```

## `decompress`

`decompress` computes the inverse function of `compress`, that is given a string and two start and end indices (in the format in which they are returned by your `compress`), return the two original strings. You need only handle valid inputs. The following equality should hold for all strings `s1`, `s2`:

```
(s1, s2) == decompress (compress (s1, s2))

```

**Examples:** (inverses of `compress` examples)

```
decompress "deabcd" ((2,5),(0,3)) -> "abcd" "deab"
decompress "abcd" ((0,3),(1,2))   -> "abcd" "bc"

decompress "abcdef" ((0,2),(3,5)) -> "abc" "def"
 or (whichever version your "compress" generates)
decompress "defabc" ((3,5),(0,2)) -> "abc" "def"

```

## Scoring

Your score is the size of the string returned by calling `compress("<code of compress>", "<code of decompress>")`. As this is a lower score is better.

**Example:**

Assume the code for your function `compress` is `c=abcd` and the code for `decompress` is `d=efghi`. Then `compress("c=abcd", "d=efghi")` yields `"c=abcd=efghi"` (and the indices, but those don't affect scoring) so the score is `length "c=abcd=efghi" = 12`.

## Additional Rules

* In the spirit of this challenge, your `compress` and `decompress` **must overlap** in at least one character. You may achieve this trivially by adding a comment, but note that doing so will increase your score and there might be shorter solutions using inherently overlapping code.
* `compress` and `decompress` should be able to handle strings containing any printable ASCII characters as well as all characters you used to define `compress` and `decompress`.
* The indices can be zero- or one-indexed.
* Your programs or functions don't have to actually be named `compress` and `decompress`.

# Answer
# GNU Prolog, 105 points

```
s(U,L/M,C):-prefix(A,C),length(A,M),suffix(U,A),length(U,L).
o(A-B,C-X-Y):-length(C,_),s(A,X,C),s(B,Y,C).

```

(This requires GNU Prolog because `prefix` and `suffix` are not portable.)

Prolog has one interesting, major advantage for this challenge; you can write a function to handle multiple call patterns (i.e. not only can you give the function an input to get a corresponding output, you can give the function an output to get the corresponding input). As such, we can define a function that can handle both compression and decompression, leading to a 105-byte submission that defines a function `o` that works both ways round. (Incidentally, I mostly wrote it as a decompressor – as it's simpler – and got the compressor "for free". ) In general, we could expect a very short program in Prolog for this task, if not for the fact that it's so bad at string handling (both in terms of missing primitives, and in terms of the primitives in question having terribly long names).

The first argument to `o` is a tuple of strings, e.g. `"abcd"-"deab"`. The second argument has a form like `"deabcd"-4/6-4/4`; this is a fairly standard nested tuple, and means that the string is "deabcd", the first string has length 4 and ends at the sixth character, the second string has length 4 and ends at the fourth character. (Note that a string in GNU Prolog is just a list of character codes, which makes debugging annoying because the implementation prefers the latter interpretation by default.) If you give `o` one argument, it'll output the other for you (thus working as a compressor if you give the first argument, and a decompressor if you give the second). If you give it both arguments, it'll verify that the compressed representation matches the strings given. If you give it zero arguments, it'll generate output like this:

```
| ?- o(X,Y).
X = []-[]
Y = []-0/0-0/0 ? ;

X = []-[]
Y = [_]-0/0-0/0 ? ;

X = []-[A]
Y = [A]-0/0-1/1 ? ;

…many lines later…

X = [A]-[B,A,C]
Y = [B,A,C]-1/2-3/3 ? ;

```

The above description of the I/O format is pretty much entirely just a description of the program, too; there's not very much in the program at all. The only subtlety is to do with evaluation order hints; we need to ensure that the program doesn't just use a search strategy that's guaranteed to terminate, but also produces the shortest possible output string.

When compressing, we start with `length(C,_)` ("`C` has a length"), which is a trick that I've used in many Prolog and Brachylog answers; if this is the first thing Prolog sees, it'll cause it to prioritise reducing the length of `C` over anything else. This ensures that we have a minimum-length `C`. The ordering of the constraints in `s` is carefully chosen so that the search will take a finite time for each possible candidate length of `C`; `A` is constrained by `C` (we don't know `C`, but we do know the target value we have for its length), `M` by `A`, `U` by `A`, and `L` by `U`, so none of the searches can take unlimited time.

When decompressing, we're given `C` directly by the user. This again ensures the program will run in finite time, due to the same sequence of constraints. (People who are aware of Prolog's evaluation order will note that the definition of `s` is very inefficient when decompressing; placing `length(A,M)` and `length(U,L)` first would be faster, but moving `length(A,M)` to the start could cause an infinite loop when compressing because neither `A` nor `M` is bound by anything at the time.)
> 25 votes

# Answer
# Brachylog, ~~50~~ 46 bytes

```
{Ċ∧Lċ₂l∧Lgj:?z{tT∧?h~cṪhlI∧ṪbhTl:I+-₁:I↔}ᵐ:L}

```

Try it online!

**Decompress:**

```
~{Ċ∧Lċ₂l∧Lgj:?z{tT∧?h~cṪhlI∧ṪbhTl:I+-₁:I↔}ᵐ:L}

```

Try it online!

*Saved 5 bytes thanks to @ais523*

### Explanation

The good side of declarative languages is that we can reuse the same code for both compressing and decompressing. As such, the code for compress is *exactly* the same as for *decompress*, with an additional `~` at the beginning.

This `~` tells Brachylog to reverse the order of arguments (that is, use the Input as output and the Output as input). Since compress has no `~`, it actually runs the predicate in the standard order. Since decompress has only one, it runs it with the Input as output and the Output as input.

That way, we can use the same code (modulo that extra `~`) to both compress and decompress: compressing is providing the two strings as input and a variable as output, and decompressing is providing the indexes and compressed string as output and a variable as Input.

Obviously this also means that we have to be a bit explicit about our compressing code, so that the interpreter is capable of running it "backwards". This is why the compressor itself is a bit long.

Here is a breakdown of the code for Compress (and thus also of decompress):

```
{……………………………………………………………………}   Call that predicate the normal way (with swapped arguments
                                 for decompress)
   Ċ                           Input has two elements
   ∧Lċ₂l                       L is a string of any length (measuring its length forces it to
                                 take a specific length from 0 to +inf)
   ∧Lgj                        The list [L,L]
       :?z                     The list [[L, First elem of Input],[L,second elem of input]]
          {………………………………}ᵐ:L    Final output is the [M,L] where M is the result of mapping
                                 the predicate below on both elements of the zip
           tT                  The second element of the input is T
           ∧?h~cṪ              Anticoncatenate the first element of the input into [A,B,C]
           hlI                 I = length(A)
           ∧ṪbhTl:I+-₁         J = length(T) + I - 1
           :I↔                 Output = [I,J]

```
> 13 votes

# Answer
# Jelly, ~~58~~ 50 bytes

-1 byte thanks to ais523 (use  for a two-byte string)

This may well be quite golfable...

**Compression** takes two string arguments and returns a list:
`[[[startA, lengthA], [startB, lengthB]], compressedString]`

```
w³;w⁴$
0;J⁸ḣ;€
ç;ç@ÑẠ$ÐfLÐṂṪµ³,⁴L€ż@Ñ,

```

**Decompression** takes one argument (such a list) and returns two\* strings:

```
,
⁾ṫḣżFv
Ḣç€Ṫ

```

Overlapped code:

```
w³;w⁴$
0;J⁸ḣ;€
ç;ç@ÑẠ$ÐfLÐṂṪµ³,⁴L€ż@Ñ,
⁾ṫḣżFv
Ḣç€Ṫ

```

One-indexed.

* this may not be obvious due to Jelly's implicit print formatting, so the code at TryItOnline linked to above has an extra byte (a `Y` at the end) to insert a line feed between the two in the printed output.

I started with a single program, which used the depth of the first (or only) argument to decide between compression and decompression, but having an unused link in the decompression code (the first line) and a single overlapping byte is shorter by seven bytes.

### How?

```
ç;ç@ÑẠ$ÐfLÐṂṪµ³,⁴L€ż@Ñ, - Compression: stringA, stringB
ç                       - call the last link (2) as a dyad
  ç@                    - call the last link (2) as a dyad with reversed arguments
 ;                      - concatenate (gives all overlapping strings)
       Ðf               - filter keep:
      $                 -     last two links as a monad
    Ñ                   -         call the next link (1) as a monad
     Ạ                  -         All? (no zeros exist in that result)
          ÐṂ            - filter keep with minimal:
         L              -     length
            Ṫ           - tail (for when more than one exists)
             µ          - monadic chain separation (we now have the compressed string)
              ³,⁴       - [stringA, stringB]
                 L€     - length of €ach
                   ż@   - zip with reversed arguments with
                     Ñ  - next link (1) as a monad with the compressed string
                      , - paired with the compressed string

J0;⁸ḣ;€ - Link 2, possible overlaps: stringL, stringR
J       - range(length(stringL)) - [1,2,...,length(stringL)]
 0;     - zero concatenate       - [0,1,2,...,length(stringL)]
   ⁸    - stringL
    ḣ   - head (vectorises)      - [empty string, first char, first two, ..., stringL]
     ;€ - concatenate €ach with stringR

w³;w⁴$ - Link 1, substring indexes: stringX
w³     - first index of first program argument in stringX or 0 if not found
  ;    - concatenated with
     $ - last two links as a monad
   w⁴  -     first index of second program argument in stringX or 0 if not found

```

```
Ḣñ€Ṫ - Decompression: [[[startA, lengthA], [startB, lengthB]], compressedString], ?
Ḣ    - head - [[startA, lengthA], [startB, lengthB]]
   Ṫ - tail - compressedString
 ç€  - call the last link (2) as a dyad for €ach of the left list
     -- extra Y atom at TIO joins the resulting list of two strings with a line feed.

⁾ṫḣżFv - Link 2, extract a substring: [start, length], string
⁾ṫḣ    - string "ṫḣ"
   ż   - zip with [start, length] to yield [['ṫ', start],['ḣ', length]]
    F  - flatten, making a list of characters
     v - evaluate as Jelly code with the string as an argument
       - this evaluates as string.tail(start).head(length) yielding the substring

, - Link 1: only here to make an overlap with the compression program.

```
> 4 votes

---
Tags: string, code-challenge, restricted-source, multiple-holes
---