# Question
Title: Solve the 15 Puzzle (the tile-sliding puzzle)
The 15 Puzzle is a famous puzzle involving sliding 15 tiles around on a 4x4 grid. Starting from a random configuration, the goal is to arrange the tiles in the correct order. Here is an example of a solved 15 Puzzle:

```
01 02 03 04
05 06 07 08
09 10 11 12
13 14 15

```

Each move on the puzzle is of the form Up/Down/Left/Right. The move "Down" consists of sliding the tile that is above the empty spot downward. The move "Right" consists of sliding a tile to the right, into the empty spot. Here is how the board looks after the moves Down and Right.

```
01 02 03 04
05 06 07 08
09 10    11
13 14 15 12

```

---

The goal of this challenge is to write a program that can output the series of moves needed to solve the 15 Puzzle. The winner is the program who solves the five test cases (below) in the fewest total moves. The generated solution does not need to be a perfect solution, it merely has to be better than the competitors. For each individual test case, the program should not take more than ten seconds on a reasonable machine.

Your program must be able to solve any puzzle that is solvable, I'm just using these five test cases as the scoring.

Your program will receive the unsolved 15 Puzzle as input in the format of a 2D array. The 2D array can be formatted according to the language used, or changed if the language does not have 2D arrays. The first element of the first sub-array will be the number in the upper left, and the last element of the first sub-array will be the number in the upper right. A `0` will be the empty space.

As output, your program should print a list of moves in the order that they need to be performed. Each step should be numbered in order to increase the usability of the results.

EDIT: Based on comments, I will allow output to be in either the form of Down/Up/etc or in the form of the coordinates of the piece to move. As this is not code golf, the most important part is to solve the puzzle.

Some other general rules involve no using an outside source, etc.

---

Test Case 1

```
([5,1,7,3],[9,2,11,4],[13,6,15,8],[0,10,14,12])

```

Example Output:

```
1: Down
2: Down
3: Down
4: Left
....

```

Test Case 2

```
([2,5,13,12],[1,0,3,15],[9,7,14,6],[10,11,8,4])

```

Test Case 3

```
([5,2,4,8],[10,0,3,14],[13,6,11,12],[1,15,9,7])

```

Test Case 4

```
([11,4,12,2],[5,10,3,15],[14,1,6,7],[0,9,8,13])

```

Test Case 5

```
([5,8,7,11],[1,6,12,2],[9,0,13,10],[14,3,4,15])

```

# Answer
> 8 votes
# PyPy, 195 moves, ~12 seconds computation

Computes optimal solutions using IDA\* with a 'walking distance' heuristic augmented with linear conflicts. Here are the optimal solutions:

```
 5  1  7  3
 9  2 11  4
13  6 15  8
 0 10 14 12
Down, Down, Down, Left, Up, Up, Up, Left, Down, Down, Down, Left, Up, Up, Up

 2  5 13 12
 1  0  3 15
 9  7 14  6
10 11  8  4
Left, Down, Right, Up, Up, Left, Down, Down, Right, Up, Left, Left, Down, Right, Right, Right, Up, Up, Left, Left, Down, Left, Up, Up, Right, Down, Down, Left, Up, Up, Right, Right, Right, Down, Left, Up, Right, Down, Down, Left, Left, Down, Left, Up, Up, Right, Up, Left

 5  2  4  8
10  0  3 14
13  6 11 12
 1 15  9  7
Left, Up, Up, Right, Right, Down, Left, Up, Left, Left, Down, Down, Right, Right, Up, Left, Left, Down, Down, Right, Right, Up, Right, Up, Left, Left, Up, Right, Down, Down, Right, Down, Left, Left, Up, Up, Left, Up

11  4 12  2
 5 10  3 15
14  1  6  7
 0  9  8 13
Down, Left, Down, Right, Up, Left, Left, Left, Down, Down, Right, Right, Right, Up, Left, Left, Left, Down, Right, Right, Up, Left, Up, Up, Left, Down, Down, Right, Down, Right, Up, Up, Right, Up, Left, Left, Left, Down, Right, Right, Right, Up, Left, Down, Left, Down, Left, Up, Up

 5  8  7 11
 1  6 12  2
 9  0 13 10
14  3  4 15
Up, Right, Down, Left, Left, Down, Left, Up, Right, Up, Right, Down, Down, Right, Up, Up, Left, Left, Left, Down, Down, Down, Right, Right, Up, Right, Down, Left, Up, Left, Up, Left, Down, Right, Down, Left, Up, Right, Down, Right, Up, Up, Left, Left, Up

```

And the code:

```
import random

class IDAStar:
    def __init__(self, h, neighbours):
        """ Iterative-deepening A* search.

        h(n) is the heuristic that gives the cost between node n and the goal node. It must be admissable, meaning that h(n) MUST NEVER OVERSTIMATE the true cost. Underestimating is fine.

        neighbours(n) is an iterable giving a pair (cost, node, descr) for each node neighbouring n
        IN ASCENDING ORDER OF COST. descr is not used in the computation but can be used to
        efficiently store information about the path edges (e.g. up/left/right/down for grids).
        """

        self.h = h
        self.neighbours = neighbours
        self.FOUND = object()

    def solve(self, root, is_goal, max_cost=None):
        """ Returns the shortest path between the root and a given goal, as well as the total cost.
        If the cost exceeds a given max_cost, the function returns None. If you do not give a
        maximum cost the solver will never return for unsolvable instances."""

        self.is_goal = is_goal
        self.path = [root]
        self.is_in_path = {root}
        self.path_descrs = []
        self.nodes_evaluated = 0

        bound = self.h(root)

        while True:
            t = self._search(0, bound)
            if t is self.FOUND: return self.path, self.path_descrs, bound, self.nodes_evaluated
            if t is None: return None
            bound = t

    def _search(self, g, bound):
        self.nodes_evaluated += 1

        node = self.path[-1]
        f = g + self.h(node)
        if f > bound: return f
        if self.is_goal(node): return self.FOUND

        m = None # Lower bound on cost.
        for cost, n, descr in self.neighbours(node):
            if n in self.is_in_path: continue

            self.path.append(n)
            self.is_in_path.add(n)
            self.path_descrs.append(descr)
            t = self._search(g + cost, bound)

            if t == self.FOUND: return self.FOUND
            if m is None or (t is not None and t < m): m = t

            self.path.pop()
            self.path_descrs.pop()
            self.is_in_path.remove(n)

        return m

def slide_solved_state(n):
    return tuple(i % (n*n) for i in range(1, n*n+1))

def slide_randomize(p, neighbours):
    for _ in range(len(p) ** 2):
        _, p, _ = random.choice(list(neighbours(p)))
    return p

def slide_neighbours(n):
    movelist = []
    for gap in range(n*n):
        x, y = gap % n, gap // n
        moves = []
        if x > 0: moves.append(-1)    # Move the gap left.
        if x < n-1: moves.append(+1)  # Move the gap right.
        if y > 0: moves.append(-n)    # Move the gap up.
        if y < n-1: moves.append(+n)  # Move the gap down.
        movelist.append(moves)

    def neighbours(p):
        gap = p.index(0)
        l = list(p)

        for m in movelist[gap]:
            l[gap] = l[gap + m]
            l[gap + m] = 0
            yield (1, tuple(l), (l[gap], m))
            l[gap + m] = l[gap]
            l[gap] = 0

    return neighbours

def slide_print(p):
    n = int(round(len(p) ** 0.5))
    l = len(str(n*n))
    for i in range(0, len(p), n):
        print(" ".join("{:>{}}".format(x, l) for x in p[i:i+n]))

def encode_cfg(cfg, n):
    r = 0
    b = n.bit_length()
    for i in range(len(cfg)):
        r |= cfg[i] << (b*i)
    return r

def gen_wd_table(n):
    goal = [[0] * i + [n] + [0] * (n - 1 - i) for i in range(n)]
    goal[-1][-1] = n - 1
    goal = tuple(sum(goal, []))

    table = {}
    to_visit = [(goal, 0, n-1)]
    while to_visit:
        cfg, cost, e = to_visit.pop(0)
        enccfg = encode_cfg(cfg, n)
        if enccfg in table: continue
        table[enccfg] = cost

        for d in [-1, 1]:
            if 0 <= e + d < n:
                for c in range(n):
                    if cfg[n*(e+d) + c] > 0:
                        ncfg = list(cfg)
                        ncfg[n*(e+d) + c] -= 1
                        ncfg[n*e + c] += 1
                        to_visit.append((tuple(ncfg), cost + 1, e+d))

    return table

def slide_wd(n, goal):
    wd = gen_wd_table(n)
    goals = {i : goal.index(i) for i in goal}
    b = n.bit_length()

    def h(p):
        ht = 0 # Walking distance between rows.
        vt = 0 # Walking distance between columns.
        d = 0
        for i, c in enumerate(p):
            if c == 0: continue
            g = goals[c]
            xi, yi = i % n, i // n
            xg, yg = g % n, g // n
            ht += 1 << (b*(n*yi+yg))
            vt += 1 << (b*(n*xi+xg))

            if yg == yi:
                for k in range(i + 1, i - i%n + n): # Until end of row.
                    if p[k] and goals[p[k]] // n == yi and goals[p[k]] < g:
                        d += 2

            if xg == xi:
                for k in range(i + n, n * n, n): # Until end of column.
                    if p[k] and goals[p[k]] % n == xi and goals[p[k]] < g:
                        d += 2

        d += wd[ht] + wd[vt]

        return d
    return h

if __name__ == "__main__":
    solved_state = slide_solved_state(4)
    neighbours = slide_neighbours(4)
    is_goal = lambda p: p == solved_state

    tests = [
        (5,1,7,3,9,2,11,4,13,6,15,8,0,10,14,12),
        (2,5,13,12,1,0,3,15,9,7,14,6,10,11,8,4),
        (5,2,4,8,10,0,3,14,13,6,11,12,1,15,9,7),
        (11,4,12,2,5,10,3,15,14,1,6,7,0,9,8,13),
        (5,8,7,11,1,6,12,2,9,0,13,10,14,3,4,15),
    ]

    slide_solver = IDAStar(slide_wd(4, solved_state), neighbours)

    for p in tests:
        path, moves, cost, num_eval = slide_solver.solve(p, is_goal, 80)
        slide_print(p)
        print(", ".join({-1: "Left", 1: "Right", -4: "Up", 4: "Down"}[move[1]] for move in moves))
        print(cost, num_eval)

```

# Answer
> 6 votes
# JavaScript (ES6) total steps 329 for all 5 test cases in ~1min

**Edit** Same strategy, different targets, better solution. Slower ...

This is more or less how I solve it by hand: using intermediate targets After each target the relative tiles are not moved again Each intermediate target is reached using a parametric BSF function. The 2 params are the loop condition L (repeat while true) and the select condition S (select what tile can be moved). The steps:

1. Place 1 top/left
2. Place 2
3. Place 5
4. Place 3,4 - top row ok
5. Place 9,13 - left column ok
6. All the rest

*Side note* I don't check the position of tiles 14 and 15. Unsolvable puzzles like `[11,4,12,2,,15,10,3,5,,14,1,6,7,,0,9,8,13]` will have 14 and 15 swapped.

```
F=b=>(
  s=[],
  [[_=>b[0]!=1, (o,p)=>b[o+p]]
  ,[_=>b[1]!=2, (o,p)=>(p=b[o+p])>1&&p]
  ,[_=>b[5]!=5, (o,p)=>(p=b[o+p])>2&&p]
  ,[_=>b[2]!=3|b[3]!=4, (o,p)=>(p=b[o+p])>2&&p!=5&&p]
  ,[_=>b[10]!=9|b[15]!=13, (o,p)=>(p=b[o+p])>5&&p]
  ,[_=>b[6]!=6|b[7]!=7|b[8]!=8|b[11]!=10|b[12]!=11|b[13]!=12|b[18]!=0, (o,p)=>(p=b[o+p])>5&&p!=9&&p!=13&&p]
  ].forEach(([L,S])=>{
    for(v={},v[b]=1,t=0,m=[];L();)
    {
      b.forEach((x,p)=>
        x=='0'&&[-1,5,1,-5].forEach((o,d)=>
          (x=S(o,p))&&(c=b.slice(0),c[p]=x,c[o+p]=0,v[k=''+c]?0:v[k]=m.push([c,s.concat(d)]))
        )
      );[b,s]=m[t++]
    }
  }),
  ,s.map((d,i)=>i+': '+'RULD'[d]).join('\n') // multi line output
  // ,s.map(d=>'RULD'[d]).join(' ') // single line output (easier to test)
)

```

Open snippet to test or play (Firefox only)

```
F=b=>(
  s=[],
  [[_=>b[0]!=1, (o,p)=>b[o+p]]
  ,[_=>b[1]!=2, (o,p)=>(p=b[o+p])>1&&p]
  ,[_=>b[5]!=5, (o,p)=>(p=b[o+p])>2&&p]
  ,[_=>b[2]!=3|b[3]!=4, (o,p)=>(p=b[o+p])>2&&p!=5&&p]
  ,[_=>b[10]!=9|b[15]!=13, (o,p)=>(p=b[o+p])>5&&p]
  ,[_=>b[6]!=6|b[7]!=7|b[8]!=8|b[11]!=10|b[12]!=11|b[13]!=12|b[18]!=0, (o,p)=>(p=b[o+p])>5&&p!=9&&p!=13&&p]
  ].forEach(([L,S])=>{
    for(v={},v[b]=1,t=0,m=[];L();)
    {
      b.forEach((x,p)=>
        x=='0'&&[-1,5,1,-5].forEach((o,d)=>
          (x=S(o,p))&&(c=b.slice(0),c[p]=x,c[o+p]=0,v[k=''+c]?0:v[k]=m.push([c,s.concat(d)]))
        )
      );[b,s]=m[t++]
    }
  }),
  //,s.map((d,i)=>i+': '+'RULD'[d]).join('\n') // multi line output
  //,s.map(d=>'RULD'[d]).join(' ') // single line output (easier to test)
  s
)
B.value=PZ.value,show()

function show(s='') {
  var b = eval(B.value)
  var t = b.map((c,i)=>'<td>'+c+'</td>').join()
  .replace(/,,/g,'</tr><tr>').replace(/,/g,'')
  G.innerHTML='<tr>'+t+'</tr>'
  S.value=s
}
function solve() {
  show('... solving ...')
  var b = eval(B.value)
  setTimeout(_=>{
    var s = F(b), zp = b.indexOf(0), sp = 0
    S.value=s.map(d=>'RULD'[d]).join(' ');
    (A=_=>{
      d=[-1,5,1,-5][m=s[sp++]]
      b[zp]=b[zp+d],zp+=d,b[zp]=0
      var t = b.map((c,i)=>'<td>'+c+'</td>').join()
      .replace(/,,/g,'</tr><tr>').replace(/,/g,'')
      G.innerHTML='<tr>'+t+'</tr>'
      if (sp<s.length)
        setTimeout(A, 300);
    })()
  },100)
}
```

```
#D { position: relative }
#D input { position: absolute; width: 300px; top:2px; left:2px; border:0 none }
#D select { position: relative; width: 400px; height:1.8em; top:0; left:0; }
textarea{ width: 600px; height: 40px }
td{ width: 1.5em; text-align:right }
```

```
Puzzles (select or edit)
<div id=D>
<select id=PZ onchange="B.value=PZ.value,show()">
<option>[5,1,7,3,,9,2,11,4,,13,6,15,8,,0,10,14,12]</option>
<option>[2,5,13,12,,1,0,3,15,,9,7,14,6,,10,11,8,4]</option>
<option>[5,2,4,8,,10,0,3,14,,13,6,11,12,,1,15,9,7]</option>
<option>[11,4,12,2,,5,10,3,15,,14,1,6,7,,0,9,8,13]</option>
<option>[5,8,7,11,,1,6,12,2,,9,0,13,10,,14,3,4,15]</option>
</select>
<button onclick="solve()">Solve</button>
<input id=B>
</div>
<textarea id=S></textarea>
<table id=G></table>
```

**Test suite** In Firefox/FireBug console

```
T=~new Date
;[[5,1,7,3,,9,2,11,4,,13,6,15,8,,0,10,14,12]
,[2,5,13,12,,1,0,3,15,,9,7,14,6,,10,11,8,4]
,[5,2,4,8,,10,0,3,14,,13,6,11,12,,1,15,9,7]
,[11,4,12,2,,5,10,3,15,,14,1,6,7,,0,9,8,13]
,[5,8,7,11,,1,6,12,2,,9,0,13,10,,14,3,4,15]]
.forEach(t=>console.log(t+'',F(t)))
console.log('Time ms ',T-=~new Date)

```

*Output*

```
"5,1,7,3,,9,2,11,4,,13,6,15,8,,0,10,14,12" "D D D L U L D L U R R U U L D D L U U"
"2,5,13,12,,1,0,3,15,,9,7,14,6,,10,11,8,4" "D R U L U L L U R D L D R D L U R U L D R D L U R U L U R R R D L L U R D R U L L D L D R U U L D R U R D L U L D D R R U L U L D R U L"
"5,2,4,8,,10,0,3,14,,13,6,11,12,,1,15,9,7" "R U U L D D R U L D D R U U L L D D R U L D L U U R R D L U R R D L L U L D D R U U L D D R U U U R R D L L U R R D L L L U R D D L U R D R U U L L D R D L U U"
"11,4,12,2,,5,10,3,15,,14,1,6,7,,0,9,8,13" "D L D R U L D D R U L L D L U R R D L U R U R D L U R U L L D R D L L D R U U L D R D L U R U U L D R R U L D R R U L L D L D R U U L D R R D L L U U R D R U L L"
"5,8,7,11,,1,6,12,2,,9,0,13,10,,14,3,4,15" "D D R U L L L D R U R D L U U R R D L U L U R D D L U U L D D D R U U L D D R U U U R D R U L D D L U U R D R U L D L L D R U L U R D L D R R U L L U R D D L U U"
"Time ms " 62234

```

# Answer
> 3 votes
I started working on this problem and wanted to contribute with my code so far. As stated by Gareth, the problem is comparable to the 8-tile puzzle and so the code is based on the magnificient solution of Keith Randall and thus in Python. This solution can solve all 5 test cases with a total sum of less than 400 moves, and other puzzles, too. It contains an optimized and a brute force solution. The code is a bit bloated by now. Output is abbrevated like "llururd.." Hope its helpful. http://www.penschuck.org/joomla/tmp/15Tile.txt (explanation) http://www.penschuck.org/joomla/tmp/tile15.txt (python code)

```
# Author: Heiko Penschuck
# www.penschuck.org
# (C) 2012

# import os;os.chdir('work')
# os.getcwd()

# def execfile(file, globals=globals(), locals=locals()):
#   with open(file, "r") as fh: exec(fh.read()+"\n", globals, locals)
#
#
# execfile("tile15.py");
#
## run these
# solve_brute();
# solve();

# some boards to play with
board2=(15,14,7,3,13,10,2,9,11,12,4,6,5,0,1,8);
# best: 76(52)
#    72(56)
#   68(51)      uurddlurrulldrrdllluuruldrddlururulddruurdllldrurddlurdruuldrdluurdd

board3=(13, 8, 9, 4, 15, 11, 5, 3, 14, 6, 12, 7, 1, 10, 2, 0)
# best: 106(77)
#best: 90(64)   ullldruuldrrdrlluurulldrrdldluruulddrulurrdrddlluuurdldrrulddrulldrurullldrdluurrrddllurdr

board4=(4, 8, 12, 1, 13, 7, 3, 11, 9, 15, 6, 14, 5, 2, 10, 0) ;# best  100(74)

board5=(15,2,3,4,5,6,7,8,9,10,11,12,13,1,14,0); # best 44(32)
board6=( 1, 2,  3,  4, 6, 11,  0, 12, 8, 14,  9, 13, 5, 10,  7, 15);

# testcases
board7=(5,1,7,3,9,2,11,4,13,6,15,8,0,10,14,12); #   15 (7)
board8=(2,5,13,12,1,0,3,15,9,7,14,6,10,11,8,4); #  124 (94)
board9=(5,2,4,8,10,0,3,14,13,6,11,12,1,15,9,7) ; #  72 (56)
board10=(11,4,12,2,5,10,3,15,14,1,6,7,0,9,8,13) ;# 71 (57)
board11=(5,8,7,11,1,6,12,2,9,0,13,10,14,3,4,15) ;# 99 (73)

board12=(1,2,3,4,5,6,7,8,9,10,11,12,13,0,14,15); #pretty simple board
board13=(4, 10, 5, 12, 11, 7, 15, 2, 13, 1, 14, 8, 6, 3, 9, 0)

board=board3 ; # used by solve()
bboard=list(board) ;# used by solve_brute()

# init
clean=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0)
i=0;
solution={};
invsolution={};
E={board:0}

# derived from Keith Randall 8-tile solution
# a: a board, d: offset to move from i: index in board
def Y(a,d,i):
 b=list(a); # b is now an indexable board
 b[i],b[i+d]=b[i+d],0; # make a move (up down left right)
 b=tuple(b); # now back to searchable
 if b not in E:E[b]=a;# store new board in E

def Calc():
 ii=0;
 # memory error when x is 21
 for x in ' '*14:
  if ii>10:
   print(ii);
  ii+=1
  for a in E.copy():
   # for all boards, make possible moves (up,left,right,down) and store the new boards
   i=list(a).index(0)
   if i>3:Y(a,-4,i)
   if i%4:Y(a,-1,i)
   if i%4 <3:Y(a,1,i)
   if i<12:Y(a,4,i)

def weigh(a,goal):
    factor=[26,8,4,6, 8,8,4,4, 4,4,1,1, 3,2,1,0]
    weight=0;
    for element in a:
        i=list(a).index(element);
        ix,iy=divmod(i,4); # ist
        if element == 0:
            # special for gap
            weight=weight+ix;
            #weight+=(ix+iy)
            continue;
        i=list(a).index(element);
        ix,iy=divmod(i,4); # ist
        j=list(goal).index(element);
        sx,sy=divmod(j,4); # soll
        #k=list(a).index(0); # gap
        #kx,ky=divmod(k,4)
        # try solving from topleft to bottom right (because clean board has gap at bottomright)
        tmp= abs(sx-ix)*abs(sx-ix)*factor[j]+ abs(sy-iy)*abs(sy-iy)*factor[j]
        #tmp += ((sx!=ix )& (sy!=iy)) *(4-sx)*(4-sy)*4
        weight+=tmp
        #(10-sx-sy-sy)
        # 8*abs(sx-ix) + (16-j)*(sx!=ix)
        #print('%2d   %2d_%2d (%2d_%2d)=> %d'%(element,i,j,(sx-ix),(sy-iy),weight))
    return weight

# read numbers seperated by a whitespace
def readboard():
    global E,D,board,clean,i
    reset()
    g=[]
    for x in' '*4:g+=map(int,input().split())
    board=tuple(g)

# read 'a' till 'o'
def readasciiboard():
    global E,D,board,clean,i
    trans={"0":0,"a":1,"b":2,"c":3,"d":4,"e":5,"f":6,"g":7,"h":8,"i":9,"j":10,"k":11,"l":12,"m":13,"n":14,"o":15}
    reset()
    g=[]
    vec=tuple(input().split());
    for x in vec: g.append(trans[x])
    board=tuple(g)

def printasciiboard(a):
    trans={"0":0,"a":1,"b":2,"c":3,"d":4,"e":5,"f":6,"g":7,"h":8,"i":9,"j":10,"k":11,"l":12,"m":13,"n":14,"o":15}
    itrans={}
    for x in trans: itrans[trans[x]]=x
    g=[]
    for x in a: g.append(itrans[x])
    for i in(0,4,8,12): print('%s %s %s %s'%tuple(g[i:i+4]))

# find the board with the smallest weight
def minimum():
    global minn,E,clean
    minn=1111111;# start with a huge number
    qq=board
    for q in E:
        if weigh(q,clean) < minn:
            minn=weigh(q,clean)
            qq=q
    return qq

# run this and printsolution()
# (you might have to reverse the order of the printed solution)
def solve():
    global start,board,E,clean,minn,solution
    start=board;
    solution={};
    E={ board:0 }
    for x in range(0,11):
        Calc(); # walks all possible moves starting from board to a depth of 10~20 moves
        if clean in E:
            print('Solution found')
            q=clean;
            tmp=[];
            while q:
                tmp.append(q)
                q=E[q]
            for x in reversed(tmp):
                solution[len(solution)]=x;
            printsolution();
            return
        q=minimum();  # calculates the "weight" for all Calc()-ed boards and returns the minimum
        #print("Len %3d"%len(E))
        print("weight %d"%minn)
#       stitch solution
        newboard=q;
        tmp=[];
        while q:
            tmp.append(q)
            q=E[q]
        for x in reversed(tmp):
            solution[len(solution)]=x;
        board=newboard;
        E={board:0}; #reset the Calc()-ed boards
    print("No Solution")

# collects and prints the moves of the solution
# from clean board to given board
# (you have to reverse the order)
def printsolution():
    global invsolution,solution,moves,clean,start
    moves=""
    g=start; # start from board to clean
    y=g
    #invsolution[clean]=0;
    for x in solution:
        # uncomment this if you want to see each board of the solution
        #print(g);
        g=solution[x];
        #sys.stdout.write(transition(y,g))
        if (transition(g,y)=="E"): continue
        moves+=transition(g,y)
        # or as squares
        #print('%10s %d %s'%("step",len(moves),transition(g,y)));
        #print(" %s -- %s "%(y,g))
        #for i in(0,4,8,12): print('%2d %2d %2d %2d'%g[i:i+4])
        y=g
    llen=len(moves)
    print(" moves%3d "%llen)
    print(moves)
    # processing moves. funny, but occysionally ud,du,lr or rl appears due to the stitching
    while 'lr' in moves:
        a,b,c=moves.partition('lr')
        moves=a+c
        llen-=2
    while 'rl' in moves:
        a,b,c=moves.partition('rl')
        moves=a+c
        llen-=2
    while 'ud' in moves:
        a,b,c=moves.partition('ud')
        moves=a+c
        llen-=2
    while 'du' in moves:
        a,b,c=moves.partition('du')
        moves=a+c
        llen-=2
    # processing moves. concatenating lll to 3l
    while 'lll' in moves:
        a,b,c=moves.partition('lll')
        moves=a+' 3l '+c
        llen-=2
    while 'rrr' in moves:
        a,b,c=moves.partition('rrr')
        moves=a+' 3r '+c
        llen-=2
    while 'uuu' in moves:
        a,b,c=moves.partition('uuu')
        moves=a+' 3u '+c
        llen-=2
    while 'ddd' in moves:
        a,b,c=moves.partition('ddd')
        moves=a+' 3d '+c
        llen-=2

    while 'll' in moves:
        a,b,c=moves.partition('ll')
        moves=a+' 2l '+c
        llen-=1
    while 'rr' in moves:
        a,b,c=moves.partition('rr')
        moves=a+' 2r '+c
        llen-=1
    while 'uu' in moves:
        a,b,c=moves.partition('uu')
        moves=a+' 2u '+c
        llen-=1
    while 'dd' in moves:
        a,b,c=moves.partition('dd')
        moves=a+' 2d '+c
        llen-=1
    print(" processed:%3d "%llen)
    print(moves)

    return

def transition(a,b):
    # calculate the move (ie up,down,left,right)
    # between 2 boards (distance of 1 move and a weight of 1 only)
    i=list(a).index(0);
    j=list(b).index(0);
    if (j==i+1): return "l"
    if (j==i-1): return "r"
    if (j==i-4): return "d"
    if (j==i+4): return "u"
    #print("transition not possible")
    return "E"

###################################################

# below this line are functions for the brute force solution only
# added for comparision
#
# its using a global variable bboard and works destructively on it

def solve_brute():
    global bboard,board;
    bboard=list(board); # working copy
    move(1,0);move(2,1);
    move(3,14); # <== additional move, move 3 out of way
    move(4,2);move(3,6);
    gap_down();gap_down();gap_right();gap_right();gap_up();gap_up();gap_up();gap_left();gap_down();
    #first line solved
    print("first line");printbboard();
    move(5,4);move(6,5);move(7,14);move(8,6);move(7,10);
    gap_down();gap_down();gap_right();gap_right();gap_up();gap_up();gap_left();gap_down();
    #second line solved (upper half)
    print("2nd line");printbboard();
    move(9,15);move(13,8);move(9,9)
    gap_down();gap_left();gap_left();gap_up();gap_right();
    print("left border");printbboard();
    #left border solved
    move(10,15);move(14,9);move(10,10);
    gap_down();movegap(1+3*4);gap_up();gap_right();
    print("left half");printbboard();
    #left half solved

    #rotating last 4 tiles 5 times
    for x in ' '*5:
        gap_right();gap_down(); # gap is now on 15
        if (bboard==[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]):
            print("solution found");printbboard();
            return;
        gap_left();gap_up();
    print("No solution found");
    printbboard();
    return

def printbboard():
    global bboard
    for i in(0,4,8,12): print('%2d %2d %2d %2d'%tuple(bboard[i:i+4]))

def gap_up():
    global bboard
    i=bboard.index(0);
    if (i<4):
        print("Err up()")
        return
    bboard[i],bboard[i-4] = bboard[i-4] , 0 ;

def gap_down():
    global bboard
    i=bboard.index(0);
    if (i>11):
        print("Err down()")
        return
    bboard[i],bboard[i+4] = bboard[i+4] , 0 ;

def gap_left():
    global bboard
    i=bboard.index(0);
    if (i%4<1):
        print("Err left()")
        return
    bboard[i],bboard[i-1]= bboard[i-1] , 0 ;

def gap_right():
    global bboard
    i=bboard.index(0);
    if (i%4>2):
        print("Err right()")
        return
    bboard[i],bboard[i+1] = bboard[i+1] , 0 ;

def movegap(d):
    global bboard;
    # d: destination location (0-15)
    k=bboard.index(0);
    ky,kx=divmod(k,4);
    dy,dx=divmod(d,4);
    # moving the gap
    while (ky>dy):
        gap_up();ky-=1;
    while (ky<dy):
        gap_down();ky+=1;
    while (kx>dx):
        gap_left();kx-=1;
    while (kx<dx):
        gap_right();kx+=1;

def move(s,d):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    dy,dx=divmod(d,4);
    #moving a number
    while (ix<dx):
        move1right(s);
        print("1right ");
        ix+=1;
    while (ix>dx):
        move1left(s);
        ix-=1;
        print("1left ");
    while(iy<dy):
        move1down(s);
        print("1down ");
        iy+=1;
    while(iy>dy):
        move1up(s);
        print("1up");
        iy-=1;

def move1up(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);
    if (ky<iy):
        # above: move 1 above, then leftorright, then 1 down
        movegap(kx+4*(iy-1))
        movegap(ix+4*(iy-1))
        movegap(ix+4*iy)
        return; # fin
    if (ky==iy):
        # if equal, then first try 1 down
        # (not nescessary if gap is right of s)
        if (kx<ix):
            if (ky<=2):
                movegap(kx+4*(iy+1))
                movegap(ix+1+4*(iy+1)); # 1right 1down of s
                movegap(ix+1+4*(iy-1)); # 1right 1up of s
                movegap(ix+4*(iy-1));# right over s
                gap_down(); # fin
                return;
            # bottom border, must go up first
            movegap(kx+4*(iy-1));
            movegap(ix+4*(iy-1));
            gap_down();
            return; # fin
        else:
            movegap(ix+1+4*iy); # move 1 right of s
            gap_up()
            gap_left()
            gap_down();
            return; # fin
    movegap(ix+1+4*ky); # move 1 right of s
    movegap(ix+1+4*(iy+1)); # move 1 right and 1 down of s
    gap_up();
    gap_up();
    gap_left();
    gap_down();

def move1left(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);
    if (ky<iy):
        # if above gap move 1 over s
        if (kx<ix):
            movegap(kx+4*iy);
            movegap(ix+4*iy);
            return;# fin
        if (kx==ix):
            #gap over s
            if (ix<3):
                # try to move under s and then left
                if (iy<3):
                    movegap(ix+1+4*ky)
                    movegap(ix+1+4*(iy+1))
                    movegap(ix-1+4*(iy+1))
                    movegap(ix-1+4*iy)
                    movegap(ix+4*iy)
                    return; #fin
            # have to move left
            movegap(kx-1+4*ky)
            movegap(ix-1+4*iy)
            movegap(ix+4*iy)
            return;# fin
        # move 1 right of s
        if (iy==3):
            # cant go under, have to go left over
            movegap(kx+4*(iy-1))
            movegap(ix-1+4*(iy-1))
            movegap(ix-1+4*iy)
            movegap(ix+4*iy);
            return; #fin
        movegap(ix+1+4*(iy-1))
        gap_down();gap_down();gap_left();gap_left();gap_up();gap_right();
        return; #fin
    if (ky==iy):
        if (kx<ix):
            movegap(ix-1+4*iy)
            gap_right();
            return; # fin
        if (ky<3):
            gap_down();
            ky+=1;
        else:
            #have to move up
            movegap(ix+4*(iy-1))
            movegap(ix-1+4*(iy-1))
            movegap(ix-1+4*iy)
            gap_right();
            return; #fin
    # gap below s
    movegap(ix+4*(iy+1));
    gap_left();gap_up();gap_right();

def move1right(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);
    if (ky<iy):
        if (kx==ix):
            movegap(kx+1+4*ky)
            movegap(kx+1+4*iy)
            movegap(ix+4*iy);
            return; #fin
        movegap(kx+4*iy)
        if (kx>ix):
            movegap(ix+4*iy);
            return; #fin
        movegap(kx+4*(iy+1))
        movegap(ix+1+4*(iy+1))
        movegap(ix+1+4*iy);
        movegap(ix+4*iy);
        return; #fin
    if (ky==iy):
        if (kx<ix):
            if (ky>2):
                # bottom row, left of s, have to move 1 up
                gap_up()
                # move 1 right 1 up of s
                movegap(ix+1+4*(ky-1));
                gap_down()
                gap_left()
                return; # fin
            # first 1 down
            movegap(kx+4*(ky+1))
            # to the right of s
            movegap(ix+1+4*(ky+1))
            gap_up()
            gap_left()
            return; # fin
        # already 1 right of s
        movegap(ix+4*iy);
        return; #fin
    # move gap 1 right and 1 down of s
    movegap(kx+4*(iy+1))
    movegap(ix+1+4*(iy+1))
    gap_up();
    gap_left();

def move1down(s):
    global bboard
    i=bboard.index(s);
    iy,ix=divmod(i,4);
    k=bboard.index(0);
    ky,kx=divmod(k,4);
    if (ky<iy):
        # gap is over s, move it below
        if (kx==ix):
            if (ix>2):
                # right border, have to move 1 to the left
                movegap(kx+4*(iy-1))
                movegap(kx-1+4*(iy-1))
                movegap(kx-1+4*(iy+1))
                gap_up();
                return; #fin
            # move right of s
            movegap(kx+4*(iy-1))
            movegap(kx+1+4*(iy-1))
            movegap(kx+1+4*(iy+1))
            movegap(kx+4*(iy+1))
            gap_up(); #fin
        movegap(kx+4*(iy+1))
        movegap(ix+4*(iy+1))
        gap_up(); #fin
    if (ky==iy):
        gap_down();
        ky+=1;
    # gap is below s, move 1 under s
    movegap(ix+4*(iy+1))
    gap_up();
    #fin

```

---
Tags: code-challenge, puzzle-solver, sliding-puzzle
---


title: Help my son find his letters

text:
# Question
Title: Help my son find his letters
### Background

Based on a game my four-year-old got from his rabbi.

The "goal" is to "find" the letters in a given order, e.g. `aecdb`. You are given a stack of letter cards, e.g. `daceb`. You can only search through the stack in the order given, albeit cyclically. When you meet a letter you need, you take that out of the stack.

### Objective

Given an order and a stack (duplicate-free permutations of each other), find the sequence of top stack letters (it is all printable ASCII) you see while playing the game.

### Step-by-step example

We need to find the order `aecdb`, given the stack `daceb`:

Top of stack `d`: Not what we are looking for (`a`), so we add it to the sequence:`d` and rotate to get the stack:`acebd`.

Top of stack `a`: Yes! so we add it to the sequence:`da` and remove it from the stack:`cebd`.

Top of stack `c`: Not what we are looking for (`e`), so we add it to the sequence:`dac` and rotate to get the stack:`ebdc`.

Top of stack `e`: Yes! so we add it to the sequence:`dace` and remove it from the stack:`bdc`.

Top of stack `b`: Not what we are looking for (`c`), so we add it to the sequence:`daceb` and rotate to get the stack:`dcb`.

Top of stack `d`: Not what we are looking for (`c`), so we add it to the sequence:`dacebd` and rotate to get the stack:`cbd`.

Top of stack `c`: Yes! so we add it to the sequence:`dacebdc` and remove it from the stack:`bd`.

Top of stack `b`: Not what we are looking for (`d`), so we add it to the sequence:`dacebdcb` and rotate to get the stack:`db`.

Top of stack `d`: Yes! so we add it to the sequence:`dacebdcbd` and remove it from the stack:`b`.

Top of stack `b`: Yes! so we add it to the sequence:`dacebdcbdb` and remove it from the stack:.

And we are done. The result is `dacebdcbdb`.

### Reference implementation

```
def letters(target, stack):
    string = ''
    while stack:
        string += stack[0]
        if stack[0] == target[0]:
            stack.pop(0)
            target = target[1:]
        else:
            stack.append(stack.pop(0))
    return string

print letters('aecdb', list('daceb'))

```

Try it online!

### Test cases

`try`, `yrt``yrtyry`

`1234`, `4321``4321432434`

`ABCDEFGHIJKLMNOPQRSTUVWXYZ`, `RUAHYKCLQZXEMPBWGDIOTVJNSF``RUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ`

`?`, `?``?`

`a`, `a` `a a`

`abcd`, `abcd``abcd`

# Answer
# APL (Dyalog Classic), 21 bytes

```
∊⊢,⊢∘⊂~¨(,\⊣⊂⍨1,2>/⍋)

```

Try it online!

This is a train equivalent to `{∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}`

gives the permutation of right argument  in left argument

`1,2>/` compare consecutive pairs with `>` and prepend a 1

`⍺⊂⍨` use the above boolean mask to split  into groups; 1s in the mask mark the start of a new group

`,\` cumulative concatenations of the groups

`(⊂⍵)~¨` complement of each with respect to

`⍵,` prepend

flatten as a single string
> 5 votes

# Answer
Three fairly different methods are giving equal byte counts.

# Python 2, 59 bytes

```
s,t=input()
for c in s*99:
 if c in t:print c;t=t.lstrip(c)

```

Try it online!

Prints each character in its own line.

---

# Python 2, 59 bytes

```
lambda s,t:[c==t[0]and t.pop(0)or c for c in s*99if c in t]

```

Try it online!

Takes lists as input, and outputs a list.

---

# Python 3, 59 bytes

```
def f(s,t):
 for c in t:p,q=s.split(c);s=q+p;print(end=p+c)

```

Try it online!
> 5 votes

# Answer
# JavaScript (ES6), 54 bytes

Takes the target as a string and the stack as an array of characters. Returns a string.

```
f=(t,[c,...s])=>t&&c+f(t.slice(c==t[0]||!s.push(c)),s)

```

### Test cases

```
f=(t,[c,...s])=>t&&c+f(t.slice(c==t[0]||!s.push(c)),s)

console.log(f('try',[...'yrt']))
console.log(f('1234',[...'4321']))
console.log(f('aecdb',[...'daceb']))
console.log(f('ABCDEFGHIJKLMNOPQRSTUVWXYZ',[...'RUAHYKCLQZXEMPBWGDIOTVJNSF']))
console.log(f('?',[...'?']))
console.log(f(' a',[...'a ']))
console.log(f('abcd',[...'abcd']))
```

### How?

At each iteration, we extract the character `c` on the top of the stack and append it to the final result. We then perform a recursive call whose parameters depend on the result of `c == t[0]`, where `t[0]` is the next expected character.

If `c` matches `t[0]`:

* we remove `c` from the target string by passing `t.slice(1)`
* we remove `c` from the stack by passing `s` unchanged

If `c` doesn't match `t[0]`:

* we let the target string unchanged by passing `t.slice(0)`
* we push `c` back at the end of the stack
> 4 votes

# Answer
## Batch, 155 bytes

```
@set/pt=
@set/ps=
@set r=
:l
@set c=%s:~,1%
@set r=%r%%c%
@if %c%==%t:~,1% set t=%t:~1%&set c=
@set s=%s:~1%%c%
@if not "%t%"=="" goto l
@echo %r%

```

Takes the target and stack as inputs on STDIN.
> 4 votes

# Answer
# Haskell, ~~49~~ 46 bytes

```
q@(a:b)#(c:d)|a==c=a:b#d|e<-d++[c]=c:q#e
a#_=a

```

Try it online!

Fairly simple. Left argument is the "goal" and the right is the stack. If the head of the goal matches the top of the stack we prepend it, and recur with the rest of the goal and the stack (without re-adding the item on top). Otherwise we prepend the top item and recur with the same goal, reading the top item to the end of the stack. When the goal is empty the pattern matching chooses the second line and the empty list is returned.

EDIT: -3 bytes thanks to @GolfWolf and @Laikoni!
> 3 votes

# Answer
# Python 2, 73 bytes

```
f=lambda o,s,S='':s and f(o[s[0]==o[0]:],s[1:]+s[:s[0]!=o[0]],S+s[0])or S

```

Try it online!

I suspect this is very highly golfable.
> 3 votes

# Answer
# Python 2, 65 bytes

```
f=lambda o,s:o and s[0]+f(o[s[0]==o[0]:],s[1:]+s[0]*(s[0]!=o[0]))

```

Try it online!
> 3 votes

# Answer
# Clean, 85 bytes

```
import StdEnv
g l[u:v][a:b]|a==u=g[a:l]v b=g[a:l][u:v](b++[a])
g l[]_=reverse l
f=g[]

```

Try it online!

Defines the partial function `f` taking `[Char]` and `[Char]`, where the first argument is the target and the second is the stack.
> 1 votes

# Answer
# \>\<\>, ~~38~~ 32 bytes

Edit: Teal pelican has a much better `><>` approach here that swaps the input methods

```
0[i:0(1$.
\~~l]1+{$[&
/?=&:&:o:{

```

Try it online!

Takes the order of the letters through the `-s` flag, and the stack through input.

### How It Works:

```
0[.... Creates a new empty stack
...... This puts the order of the letters safely away
......

..i:0(1$. Takes input until EOF (-1). This means input is in reverse
..~...    And then teleports to the ~ on this line
......

......      Gets the first character from the beginning of the order
\.~l]1+{$[& And stores it in the register before going to the next line
/.....

......     Output the bottom of the stack
......     Checks if the bottom of the stack is equal to the current character
/?=&:&:o:{ If so, go to the second line, else cycle the stack and repeat

0.....      Pop the extra 0 we collected
\~~l]1+{$[& Pop the value that was equal and get the next character from the order
/.....      And go down to the last line. This will end with an error (which could be avoid with a mere 4 extra bytes

```
> 1 votes

# Answer
# Java 8, 88 bytes

```
a->b->{for(int c:a)for(char t=0;c!=t;System.out.print(t)){t=b.poll();if(c!=t)b.add(t);}}

```

Inputs as `char[]` and `java.util.LinkedList<Character>` (`java.util.Queue` implementation)

**Explanation:**

Try it online.

```
a->b->{                        // Method with two parameters and no return-type
  for(int c:a)                 //  Loop over the characters of the char-array
    for(char t=0;c!=t;         //   Inner loop until we've found the character in the queue
        System.out.print(t)){  //     After every iteration: print the char `t`
      t=b.poll();              //    Remove the top of the queue, and save it in `t`
      if(c!=t)                 //    If this is not the character we're looking for:
        b.add(t);}}            //     Add it at the end of the queue again

```
> 1 votes

# Answer
# \>\<\>, ~~21~~ 16 bytes

```
i$\~~
=?\$:{::o@

```

Try it online!

Flow changed to utilize the empty spaces and remove extra code rerouting. (-5 bytes) - Thanks to @JoKing

# \>\<\>, 21 bytes

```
i:{:@=?v:o$!
o~i00. >

```

Try it online!

The other \>\<\> answer can be found here.

### Explanation

The stack starts with an initial set of characters using the -s flag. Input is the user given character order. This explanation will follow the flow of the code.

```
i$\        : Take input, swap the top 2 stack items then move to line 2;
             [1,2,3] -> [1,2,4,3]
  \$:      : Swap the top 2 stack items then duplicate the top item;
             [1,2,4,3] -> [1,2,3,4,4]
     {::o  : Move the stack items 1 left then duplicate the stack top twice and print one;
             [1,2,3,4,4] -> [2,3,4,4,1,1]
=?\      @ : Swap the top three stack items left 1 then do an equal comparison, if equality move to line 1 else continue;
             [2,3,4,4,1,1] -> [2,3,4,1,1,4] -> [2,3,4,1]
  \~~      : Remove the top 2 stack items;
             [2,3,4,1] -> [2,3]

```
> 1 votes

# Answer
# Perl 5, 42 + 2 (`-pl`) = 44bytes

```
for$i(<>=~/./g){/$i/;$\.=$`.$i;$_=$'.$`}}{

```

Try it online!
> 1 votes

# Answer
# Perl, 62 bytes

```
sub{$_=$_[1];for$x(@{$_[0]}){/\Q$x\E/;$z.="$`$&";$_="$'$`"}$z}

```

Takes its first argument, the order, as a list of characters and its second, the stack, as a string.

Ungolfed:

```
sub {
    $_ = $_[1];
    for $x (@{$_[0]}) {
        /\Q$_\E/;
        $z.="$`$&";
        $_ = "$'$`"
    }
    $z
}

```

You ever wonder what all those obscure regex variables were for? Clearly, they were designed for this exact challenge. We match on the current character `$x` (which unfortunately has to be escaped in case it's a regex special character). This conveniently splits the string into "before the match" `$``, "the match" `$&`, and "after the match" `$'`. In the cyclic search, we clearly saw every character before the match and put them back into the stack. We also saw the current character but didn't put it back. So we append "before the match" to the "seen" list `$z` and construct the stack out of "after the match" followed by "before the match".
> 0 votes

# Answer
# SNOBOL4 (CSNOBOL4), 98 bytes

```
	S =INPUT
	L =INPUT
R	S LEN(1) . X REM . S	:F(END)
	OUTPUT =X
	L POS(0) X =	:S(R)
	S =S X	:(R)
END

```

Try it online!

Prints each letter on a newline. Use this version to get everything to print on the same line. Takes input as stack, then target, separated by a newline.

```
	S =INPUT			;*read stack
	L =INPUT			;*read letters
R	S LEN(1) . X REM . S	:F(END)	;*set X to the first letter of S and S to the remainder. If S is empty, goto END.
	OUTPUT =X			;*output X
	L POS(0) X =	:S(R)		;*if the first character of L matches X, remove it and goto R
	S =S X	:(R)			;*else put X at the end of S and goto R
END

```
> 0 votes

# Answer
# Perl, 44 bytes

Includes `+4` for `-lF`

Give input as on STDIN as target then stack (this is the reverse order from the examples):

```
(echo daceb; echo aecdb) | perl -lF -E '$a=<>;say,$a=~s/^\Q$_//||push@F,$_ for@F'

```

If you don't mind a trailing newline this `40` works:

```
(echo daceb; echo aecdb) | perl -plE '$_=<>=~s%.%s/(.*)\Q$&//s;$_.=$1;$&%reg'

```
> 0 votes

---
Tags: code-golf, string, sequence, game, stack
---


title: Post-determined Array Sorting

text:
# Question
Title: Post-determined Array Sorting
**Input:**

* An array containing three integers: `0`, `1` and `2` in any order (i.e. `[2, 0, 1]`)
* And a string of length \>= 2 only containing alphabetic letters (both lower- and uppercase) and digits (i.e. `a1B2c3`)

**Output:**

Based on the array we sort and output the string.
How does this work?

* The array indicates the order precedence of `a-z`, `A-Z` and `0-9`, the first being `0`; second being `1`; and third being `2`.
* The individual characters of the string can then be ordered based on that.

**Example:**

* Array: `[2, 0, 1]`
* String: `a1B2c3`

Based on the array, we know our order precedence is `0-9a-zA-Z`.
Based on that, we can convert and output the string: `123acB`.

**Challenge rules:**

* For the array you can choose to use 0-indexed or 1-indexed input, so `[3, 1, 2]` is also a valid input if you prefer to use 1-indexed arrays.
* The string (both input and output) only contains valid characters: `abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`.
* If your language doesn't support arrays (or if you choose to), you are free to use strings instead of arrays for the first parameter (i.e. `012`, `[0,1,2]`, etc.).

**General rules:**

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

**Test cases:**

```
[2, 0, 1]  &  a1B2c3             ->   123acB
[2, 1, 0]  &  aAaA909UuHWw9gh2   ->   02999AAHUWaaghuw
[2, 1, 0]  &  6Bx43              ->   346Bx
[1, 0, 2]  &  jfjf33g            ->   ffgjj33
[0, 2, 1]  &  AbC13              ->   b13AC
[1, 2, 0]  &  Qfl0l              ->   Q0fll
[0, 1, 2]  &  9870abcABC         ->   abcABC0789
[0, 2, 1]  &  test123            ->   estt123
[2, 0, 1]  &  WHAT               ->   AHTW
[2, 0, 1]  &  WhAt               ->   htAW
[1, 0, 2]  &  102BACbac          ->   ABCabc012

```

# Answer
> 5 votes
# 05AB1E, ~~15~~ ~~14~~ 12 bytes

Code:

```
v²žK26ôyèÃ{?

```

Explanation:

```
v             # For each in the input array.
  žK          #   Push a-zA-Z0-9.
    26ô       #   Split into pieces of 26.
       yè     #   Get the element-th element of the array.
 ²       Ã    #   Keep the characters of that element from the second input.
          {?  #   Sort pop and print without a newline.

```

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

# Answer
> 8 votes
# Python 2, ~~67~~ 66 bytes

```
lambda s,k:`sorted(s,key=lambda c:`k.index(3-ord(c)/32)`+c)`[2::5]

```

Test it on Ideone.

# Answer
> 7 votes
## JavaScript (ES6), 87 bytes

```
(a,s)=>a.map(n=>[...s].sort().join``.replace([/[^a-z]/g,/[^A-Z]/g,/\D/g][n],``)).join``

```

If the input array gave the order, rather than the precedence, of the three ranges (this only makes a difference for `[1, 2, 0]` and `[2, 1, 0]` whose effects are swapped) then this would have worked for 80 bytes:

```
(a,s,o=c=>a[(c<'a')+(c<'A')])=>[...s].sort((a,b)=>o(a)-o(b)||(a>b)-(a<b)).join``

```

I misread the question and still got 7 upvotes with this. Feel free to remove your upvotes and give them to @CharlieWynn instead, who came up with the best correction to my approach.

```
(a,s)=>a.map(n=>s.replace([/[^a-z]/g,/[^A-Z]/g,/\D/g][n],``)).join``

```

# Answer
> 5 votes
## Pyth, ~~17~~ ~~16~~ 15 bytes

```
s@RSz@L[GrG1`UT

```

Test suite.

```
       [          array literal containing...
        G           the alphabet (lowercase)
         rG1        the alphabet, converted to uppercase
            `UT     inspect-range-10, generating the range [0,10) and
                      stringifying it, resulting in a string that contains no
                      letters and all numbers (so equivalent to '0123456789' for
                      filtering)
                    this creates ['ab...z', 'AB...Z', '01...9']

     @L           map over first (implicit) input (the ordering array) and take
                   the nth element in this array for each item
                   this gives us ['01...9', 'ab...z', 'AB...Z']

   Sz             take another line of input as a string and sort it, and then...
 @R               map over intersection: filter the line of input over presence
                    in each element in the new array
                    this results in ['123', 'ac', 'B']

s                 concatenate all and implicitly output

```

Thanks to @FryAmTheEggman for a byte and @Jakube for another!

# Answer
> 5 votes
# Javascript es6 77 bytes

```
(a,s)=>a.map(o=>s.match([/[a-z]?/g,/[A-Z]?/g,/\d?/g][o]).sort().join``).join``

```

---

```
//test
f=(a,s)=>a.map(o=>(s.match([/[a-z]/g,/[A-Z]/g,/\d/g][o])||[]).sort().join``).join``

f([2, 0, 1], "a1B2c3")             == "123acB" &&
f([2, 1, 0], "aAaA909UuHWw9gh2")   == "02999AAHUWaaghuw" &&
f([2, 1, 0], "6Bx43")              == "346Bx" &&
f([1, 0, 2], "jfjf33g")            == "ffgjj33" &&
f([0, 2, 1], "AbC13")              == "b13AC" &&
f([1, 2, 0], "Qfl0l")              == "Q0fll" &&
f([0, 1, 2], "9870abcABC")         == "abcABC0789" &&
f([0, 2, 1], "test123")            == "estt123" &&
f([2, 0, 1], "WHAT")               == "AHTW" &&
f([2, 0, 1], "WhAt")               == "htAW" &&
f([1, 0, 2], "102BACbac")          == "ABCabc012"

```

# Answer
> 5 votes
# Jelly, 13 bytes

```
2_ịØWs26¤Ff@€

```

Try it online! or verify all test cases.

### How it works

```
2_ịØWs26¤Ff@€  Main link. Arguments: k (permutation of [0, 1, 2]), s (string)

2_             Subtract the integers in k from 2, mapping [0, 1, 2] -> [2, 1, 0].
        ¤      Combine the three links to the left into a niladic chain.
   ØW          Yield the string following string.
               'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_'
     s26       Split it into chunks of 26 chars, i.e., ['A...Z', 'a...z', '0...9'].
  ị            Retrieve the chunks from the right result at the indices of the
               left result. The indices of the chunks are modular and 1-based;
               1 retrieves 'A...Z', 2 retrieves 'a...z', and 3 retrieves '0...9'.
         F     Flatten the resulting array of strings.
          f@€  Filter (swapped, each); for each character in the constructed
               string, select all occurrences of that character from s.

```

# Answer
> 4 votes
# TSQL, ~~199~~ 191 bytes

**Golfed:**

```
DECLARE @i varchar(99)='abA7B34',@s char(3)='213'

,@ varchar(99)=''SELECT @+=n FROM(SELECT top 99n FROM(SELECT top 99substring(@i,row_number()over(order by 1/0),1)n FROM sys.messages)c ORDER BY CHARINDEX(CHAR(ascii(n)/32+48),@s),n)d SELECT @

```

**Ungolfed:**

```
DECLARE @i varchar(99)='abA7B34'
-- 1 numbers, 2 upper case, 3 lower case
DECLARE @s char(3)='213'

,@ varchar(99)=''
SELECT @+=n
FROM
  (
    SELECT top 99 n
    FROM
      (
         SELECT top 99substring(@i, row_number()over(order by 1/0), 1)n
         FROM sys.messages
      )c
    ORDER BY CHARINDEX(CHAR(ascii(n)/32+48),@s),n
  )d

SELECT @

```

**Fiddle**

# Answer
> 3 votes
# APLX, 19 bytes

```
s[(∊(⎕a⎕A⎕D)[a])⍋s]

```

`⎕a⎕A⎕D` lower upper digits

`(``)[a]` reorder according to array *a*

flatten

`(``)⍋s` according to that "alphabet", give the indices that would sort string *s*

`s[``]` use that to reorder *s*

# Answer
> 2 votes
# Python 2, 121 Bytes

```
lambda a,s:"".join(sum([[sorted(filter(eval(u),s))for u in["str.islower","str.isupper","str.isdigit"]][i]for i in a],[]))

```

# Answer
> 2 votes
# Clojure, 74 bytes

```
#(apply str(mapcat sort(for[i %](re-seq([#"[a-z]"#"[A-Z]"#"[0-9]"]i)%2))))

```

For each value in first list, gets appropriate regex and apply it to the input string. The result is a list of lists of symbols which match the regex. Then sort each one and concatenates the result into one list and transform it to string.

You can see it online here: https://ideone.com/dqAkxg

# Answer
> 2 votes
## Retina, ~~43~~ 39 bytes

Byte count assumes ISO 8859-1 encoding. The trailing linefeed is significant.

```
2=`.
!$&"
T04`¶d`#^@%
O`\W?.
O`.\w+
\W

```

Input is expected to be the sort order as a zero-based list without delimiters on the first line, and the string to be sorted on the second line, e.g.

```
120
fOo42BaR

```

Try it online!

### Explanation

I will use the above input example to walk you through the code:

```
120
fOo42BaR

```

**Stage 1: Substitution**

```
2=`.
!$&"

```

The regex itself is just `.` (matches any non-linefeed character), which is surrounded with `!..."`. However, the `2=` is a *limit* telling Retina to apply the substitution only to the second match of the regex. So we get this:

```
1!2"0
fOo42BaR

```

**Stage 2: Transliteration**

```
T04`¶d`#^@%

```

A transliteration stage simply does a character-by-character substitution. The  represents a linefeed and `d` expands to `0123456789` (although we can ignore all digits after `2`). That means, this transliteration corresponds to the following mapping:

```
¶012
#^@%

```

The `04` at the front are two limits, which together indicate that only the first four characters from this set should be transliterated. That happens to be the digits on the first line, as well as the linefeed separating the two lines, so we get this:

```
@!%"^#fOo42BaR

```

At the front of the string we've now got three pairs of these characters:

```
@!
%"
^#

```

Note that the second characters of the pairs are simply in their normal ASCII order (and will always be the same). We'll use these later to sort the groups of characters in the main input into the required order.

The first characters are bit more interesting: their significance is that `%` comes before digits in the ASCII table, `@` comes before upper case letters (but after digits), and `^` comes before lower case letters (but after upper case letters). This will help us group the position markers (i.e. the second character in each pair) with the right set of characters.

**Stage 3: Sort**

```
O`\W?.

```

This is a simple sort stage. It matches two characters if the first one isn't a word character (thereby matching all three pairs I just talked about) or a single character otherwise (matching each character of the main input individually), and sorts those strings. This has two purposes: it brings the characters *within* each group in the correct order (and since sorting is stable, this order won't be messed up in the next stage), and it due to the `%@^` markers, it inserts the pairs in the right positions:

```
%"24@!BOR^#afo

```

**Stage 4: Sort**

```
O`.\w+

```

This stage sorts all matches of the `.\w+` regex which, due to greediness, matches one position marker (i.e. one of `!"#`) together with all the word characters after it. That is, it sorts these three strings, whose order is determined solely by the marker character:

"24 !BOR #afo

While this shuffles around those markers (while leaving the other three markers in place), most importantly it brings the digits and letters in the correct order:

```
%!BOR@"24^#afo

```

**Stage 5: Substitution**

```
\W

```

All that's left is a little clean-up, where we remove all the markers by matching them and replacing them with nothing.

# Answer
> 2 votes
## Haskell, ~~62~~ 63 bytes

```
a#b=[c|i<-b,c<-[' '..],d<-a,d==c,div(fromEnum c)16==[6,4,3]!!i]

```

Usage example: `"cD12ab" # [2,0,1]` -\> `"12abcD"`.

How it works:

```
i<-b                                  -- loop i through the input array
   [c|   c<-[' '..]]                  -- loop through all chars c
       d<-a                           -- loop through all chars d in the input string
       d==c                           -- and keep those that are in the input string
       div(fromEnum c)16==[6,4,3]!!i  -- and where the the ascii value divided by
                                      -- 16 equals the number from [6,4,3] indexed
                                      -- by the current i

```

Edit: @Christian Sievers found a bug. Thanks! Fixed for 1 additional byte.

# Answer
> 2 votes
# Ruby, 56 bytes

Ported from @Dennis answer.

```
->a,s{s.chars.sort_by{|c|a.index(3-c.ord/32).to_s+c}*''}

```

An alternate 58 bytes solution that I like better, inspired by @Neil and modified slightly from his answer.

```
->a,s{a.map{|i|s.scan([/[a-z]/,/[A-Z]/,/\d/][i]).sort}*''}

```

Try either version online! (commented-out version is the alternate solution)

# Answer
> 2 votes
# JavaScript (ES6), 65

Note: 'natural' ASCII order is 0-9, A-Z, a-z, that is just the opposite of the OP 0,1,2. So

* order the string adding invalid chars to separate runs
* split it in 3 segmenents - invalid chars mark each
* get segments one by one in the requested order
* reassemble

```
s=>w=>w.map(w=>[...'^@'+s].sort().join``.split(/\W/)[2-w]).join``

```

```
F=s=>w=>w.map(w=>[...'^@'+s].sort().join``.split(/\W/)[2-w]).join``

;[['201','a1B2c3','123acB']
,['210','aAaA909UuHWw9gh2','02999AAHUWaaghuw']
,['210','6Bx43','346Bx']
,['102','jfjf33g','ffgjj33']
,['021','AbC13','b13AC']
,['120','Qfl0l','Q0fll']
,['012','9870abcABC','abcABC0789']
,['021','test123','estt123']
,['201','WHAT','AHTW']
,['201','WhAt','htAW']
,['102','102BACbac','ABCabc012']]
.forEach(t=>{
  var w=t[0],s=t[1],k=t[2], r=F(s)([...w])
  console.log(w,s,r,(r==k?'OK':'KO (expected '+k+')'))
})
```

# Answer
> 2 votes
# Stax, 15 bytes

```
┐°!'àÉgYg8∟╗`╖ë

```

Run and debug it online

This 15 byte submission is packed into a variant of the CP437 character set. The corresponding ascii representation takes 18 bytes:

```
EVlVd+26/s@:fs{[Io

```

Pretty sure it can be further trimmed down though.

```
E                   Put the two inputs on main stack
 Vl                 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
   Vd               "0123456789"
     +              Concatenate
      26/           Partition to blocks of size 26 (array `a`)
         s@         Index array `a` with the input index array
           :fs      Flatten to get a string `s`
              {[Io  Order the input string
                        Using the char array `s` as the key
                    Implicit output

```

`VlVd+` can also be `VLA|(`, which left rotates the `0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ` by ten elemenets. The whole code can also be `VlVd+26/,e@:f,{[Io`, which reads the input stack twice instead of reading them all at the beginning to the main stack, and uses a different (more traditional) input format, as shown in this.

# Answer
> 1 votes
# Dyalog APL, 22 bytes

```
s[s⍋⍨∊(819⌶⎕A)⎕A⎕D[a]]

```

`(819⌶⎕A)` fold the uppercase alphabet to lowercase

`(``)⎕A⎕D[a]` lower upper digits reordered according to array *a*

flatten

`s⍋⍨` for string *s*, get the indices that would sort *s* according to that "alphabet"

`s[``]` use that to reorder *s*

# Answer
> 1 votes
# Python 2, ~~140~~ ~~117~~ ~~101~~ ~~100~~ 99 bytes

Everyone say, "Ewww!". At least it's readable... *cough not really cough*

```
lambda l,s:`sorted(s,key=lambda c:[[c<'a',c<'A'or'Z'<c,c>'9'][l[i]]for i in 0,1,2]+[ord(c)])`[2::5]

```

**Try it online**

# Answer
> 1 votes
## PowerShell v2+, 107 bytes

```
param($n,[char[]]$s)-join(-join(($s=$s|sort)|?{$_-ge97}),-join($s|?{$_-in65..96}),-join($s|?{$_-lt58}))[$n]

```

I'm exploring algorithms using regex, but thus far they all seem longer.

Takes input as explicit array `$n` (see examples below) and string `$s` which is immediately cast to a char-array. We're then constructing three elements of a new dynamic array, each of them encapsulated with a `-join`:
\- `(($s=$s|sort)|?{$_-ge97})`
\- `($s|?{$_-in65..96})`
\- `($s|?{$_-lt58})`

The first we take `$s` and run it through `Sort-Object`. Thankfully, since we've already cast it as a char-array, it's case-sensitive sorting. That gets re-saved into `$s` and then piped to a `Where-Object` with a clause of greater than `97` (i.e., ASCII lowercase `a-z`). The second is for `A-Z` and the third for `0-9`.

Thus we now have an array of strings, where each string is composed one of the three character types and is sorted. We slice that with `[$n]` and then `-join` the result together to form our final output string. That is left on the pipeline and printing is implicit.

## Test Cases

```
PS C:\Tools\Scripts\golfing> $test = (@(2,0,1),'a1B2c3'), (@(2,1,0),'aAaA909UuHWw9gh2'), (@(2,1,0),'6Bx43'), (@(1,0,2),'jfjf33g'), (@(0,2,1),'AbC13'), (@(1,2,0),'Qfl0l'), (@(0,1,2),'9870abcABC'), (@(0,2,1),'test123'), (@(2,0,1),'WHAT'), (@(2,0,1),'WhAt'), (@(1,0,2),'102BACbac')

PS C:\Tools\Scripts\golfing> $test |%{"($($_[0]-join',')) & $($_[1])".PadRight(28)+" -> " + (.\post-determined-array-sorting.ps1 $_[0] $_[1])}
(2,0,1) & a1B2c3             -> 123acB
(2,1,0) & aAaA909UuHWw9gh2   -> 02999AAHUWaaghuw
(2,1,0) & 6Bx43              -> 346Bx
(1,0,2) & jfjf33g            -> ffgjj33
(0,2,1) & AbC13              -> b13AC
(1,2,0) & Qfl0l              -> Q0fll
(0,1,2) & 9870abcABC         -> abcABC0789
(0,2,1) & test123            -> estt123
(2,0,1) & WHAT               -> AHTW
(2,0,1) & WhAt               -> htAW
(1,0,2) & 102BACbac          -> ABCabc012

```

# Answer
> 1 votes
# 32-bit x86 machine code, 70 bytes

In hex:

```
fc31c031c95189e3ac84c0740a34cf0404880c0341ebf189fe9160ac88c2c0e805d788c652ac88c2c0e805d788c658740e6639d076029241aa92aa4e4febdc85c96175d658c3

```

This procedure expects character class sorting order to be a 3-char (0..2) NULL-terminated string in `ESI` and the string to sort in `EDI`. Sorting is done in-place using extremely sub-optimal (performance-wise) version of bubble sort.

```
0:  fc                  cld
1:  31 c0               xor eax, eax
3:  31 c9               xor ecx, ecx
5:  51                  push ecx        ;Allocate 4 bytes on the stack
6:  89 e3               mov ebx, esp    ;char EBX[4]
_loop0:                                 ;Parsing class order string
8:  ac                  lodsb
9:  84 c0               test al,al      ;Break on NULL
b:  74 0a               jz _break0
d:  34 cf               xor al, 0xCF    ;AL=~atoi(AL)
f:  04 04               add al, 4       ;'0'->3, '1'->2, '2'->1
11: 88 0c 03            mov [ebx+eax], cl    ;EBX[AL]=CL
14: 41                  inc ecx
15: eb f1               jmp _loop0
_break0:
17: 89 fe               mov esi,edi
19: 91                  xchg eax,ecx    ;ECX=0
_bsort:
1a: 60                  pusha
_cx2b:
1b: ac                  lodsb           ;Get the first char to compare
1c: 88 c2               mov dl,al       ;Save to DL
1e: c0 e8 05            shr al,5        ;Char class: [0-9]->1, [A-Z]->2, [a-z]->3
21: d7                  xlat            ;AL=EBX[AL] - priority for the char class
22: 88 c6               mov dh,al       ;... goes to DH
24: 52                  push edx        ;First "comparable char" in DX goes to the stack
25: ac                  lodsb           ;Get the second char to compare
26: 88 c2               mov dl,al       ;\
28: c0 e8 05            shr al,5        ; > Same as the above
2b: d7                  xlat            ;/
2c: 88 c6               mov dh, al      ;Second "comparable char" in DX
2e: 58                  pop eax         ;The first one goes to AX
2f: 74 0e               jz _endpass     ;ZF is set by the last 'shr', and only on AL==0
31: 66 39 d0            cmp ax,dx       ;Upper halves of 32-bit regs may contain trash
34: 76 02               jbe _sorted
36: 92                  xchg eax,edx    ;Now AX<=DX
37: 41                  inc ecx         ;Swap counter
_sorted:
38: aa                  stosb           ;Store AL in-place
39: 92                  xchg eax,edx    ;AL=DL
3a: aa                  stosb           ;Store the second char
3b: 4e                  dec esi         ;Move pointers...
3c: 4f                  dec edi         ;...back one byte
3d: eb dc               jmp _cx2b       ;Repeat with the next two chars
_endpass:
3f: 85 c9               test ecx,ecx    ;Full pass completed, checking # of swaps made
41: 61                  popa            ;Restores ECX(0), ESI, EDI. Doesn't affect flags
42: 75 d6               jnz _bsort      ;If there were changes, repeat
_end:
44: 58                  pop eax         ;Deallocate EBX[]
45: c3                  ret

```

# Answer
> 1 votes
## Emacs Lisp, 183 bytes

```
(lambda(s p)(let(l u n)(apply'concat(mapcar(lambda(l)(sort l'<))(dolist(e(string-to-list s)(mapcar(lambda(i)(nth i(list l u n)))p))(push e(cond((< ?` e)l)((< ?@ e)u)((< ?/ e)n))))))))

```

Slightly shorter than Java...

# Answer
> 1 votes
**Clojure, 77 bytes**

```
#(apply str(mapcat sort(map(group-by(fn[v](condp <(int v)90 0,57 1,2))%2)%)))

```

Not quite as short as the `re-seq` based one, and I couldn't figure out how to express that "`(apply str(mapcat sort(map(...))))`" in less space. `group-by` creates a hash-map which can be used as a function, when queried with an ingeger between 0 and 2 it returns the corresponding group, this orders the three different classes of characters.

This would be more compact than the `re-seq` solution if there were more character classes to handle as this only takes 5 extra characters / group like `57 1,` instead of 8 for expression like `#"[a-z]"`.

# Answer
> 1 votes
# , 101 bytes

```
function(a,s,o=unlist(list(letters,LETTERS,0:9)[a]))cat(o[sort(match(strsplit(s,'')[[1]],o))],sep='')

```

Creates a vector with a-z, A-Z and 0-9 in given order and reorders characters of input string to match this ordering.

Try it online!

# Answer
> 0 votes
# Java 8, ~~221~~ ~~212~~ ~~193~~ 156 bytes

I should of course try to answer my own challenge as well. :) (And as usual in Java.)

```
a->i->{for(byte c[],j=0;j<3;System.out.print(new String(c)))java.util.Arrays.sort(c=i.replaceAll("[^a-z];[^A-Z];[^0-9]".split(";")[a[j++]],"").getBytes());}

```

-28 bytes saved thanks to *@cliffroot*.

**Explanation:**

Try it here.

```
a->i->{          // Method with integer-array and String parameters and no return-type
  for(byte c[],  //  Temp byte-array
      j=0;j<3;   //  Loop from 0 to 3 (exclusive)
      System.out.print(new String(c)))
                 //    After every iteration: print the byte-array as String
    java.util.Arrays.sort(
                 //   Sort the byte-array
      c=         //    After we've replaced the byte-array with
        i.replaceAll("[^a-z];[^A-Z];[^0-9]".split(";")[a[j++]],"").getBytes());}
                 //    all bytes of the uppercase letters, lowercase letters, or digits,
                 //    depending on the next number in the input-array

```

# Answer
> 0 votes
# J, 40 bytes

```
;@:{[:(<@/:~@}./.~2-64 96 I.3&u:)'aA0'&,

```

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


title: It's raining in my terminal!

text:
# Question
Title: It's raining in my terminal!
# Challenge Description

You have to show a simulation of rain in terminal.

In the example given below its adding 100 raindrops at random (use the default random function which your language offers) coordinates, waiting for 0.2 seconds and then redrawing again until the given time expires. Any character can be used for representing the raindrop.

### Parameters

* Wait time between redrawing in seconds.
* Time for which the rain will be visible. This is just an integer representing the number of iterations. \[So, the net time for which the rain will be visible is this integer multiplied by the wait time\]
* Message to be displayed when the rain ends. (This has to be centered)
* Number of raindrops to be displayed on the screen.

### Rules

* A single byte should be used for representing a rain drop, and it can be anything, even cats and dogs.
* It doesn't have to be responsive to terminal size which means you don't have to handle the bug for varied terminal sizes. You can specify the terminal width and height on your own.
* Standard rules of golfing apply.

# Code Sample and Output

This is an ungolfed version written in python 2.7 using ncurses.

```
import curses
import random
import time

myscreen = curses.initscr()
curses.curs_set(0) # no cursor please
HEIGHT, WIDTH = myscreen.getmaxyx()
RAIN = '/' # this is what my rain drop looks like
TIME = 10

def make_it_rain(window, tot_time, msg, wait_time, num_drops):
    """
    window    :: curses window
    time      :: Total time for which it rains
    msg       :: Message displayed when it stops raining
    wait_time :: Time between redrawing scene
    num_drops :: Number of rain drops in the scene
    """
    for _ in range(tot_time):
        for i in range(num_drops):
            x,y=random.randint(1, HEIGHT-2),random.randint(1,WIDTH-2)
            window.addstr(x,y,RAIN)
        window.refresh()
        time.sleep(wait_time)
        window.erase()

    window.refresh()
    window.addstr(HEIGHT/2, int(WIDTH/2.7), msg)

if __name__ == '__main__':
    make_it_rain(myscreen, TIME, 'IT HAS STOPPED RAINING!', 0.2, 100)
    myscreen.getch()
    curses.endwin()

```

Output -

# Answer
# MATL, 52 bytes

```
xxx:"1GY.Xx2e3Z@25eHG>~47*cD]Xx12:~c!3G80yn-H/kZ"why

```

Inputs are, in this order: pause between updates, number of drops, message, number of repetitions. The monitor has size 80×25 characters (hard-coded).

GIF or it didn't happen! (Example with inputs `0.2`, `100`, `'THE END'`, `30`)

Or try it at **MATL Online**.

### Explanation

```
xxx      % Take first three inputs implicitly and delete them (but they get
         % copied into clipboard G)
:"       % Take fourth input implicitly. Repeat that many times
  1G     %   Push first input (pause time)
  Y.     %   Pause that many seconds
  Xx     %   Clear screen
  2e3    %   Push 2000 (number of chars in the monitor, 80*25)
  Z@     %   Push random permutation of the integers from 1 to 2000
  25e    %   Reshape as a 25×80 matrix, which contains the numbers from 1 to 2000
         %   in random positions
  HG     %   Push second input (number of drops)
  >~     %   Set numbers that are <= second input to 1, and the rest to 0
  47*c   %   Multiply by 47 (ASCII for '/') and convert to char. Char 0 will
         %   be displayed as a space
  D      %   Display
]        % End
Xx       % Clear screen
12:~     % Push row vector of twelve zeros
c!       % Convert to char and transpose. This will produce 12 lines containing
         % a space, to vertically center the message in the 25-row monitor
3G       % Push third input (message string)
80       % Push 80
yn       % Duplicate message string and push its length
-        % Subtract
H/k      % Divide by 2 and round down
Z"       % Push string of that many spaces, to horizontally center the message
         % in the 80-column monitor
w        % Swap
h        % Concatenate horizontally
y        % Duplicate the column vector of 12 spaces to fill the monitor
         % Implicitly display

```
> 12 votes

# Answer
## JavaScript (ES6), ~~268~~ 261 bytes

```
t=
(o,f,d,r,m,g=(r,_,x=Math.random()*78|0,y=Math.random()*9|0)=>r?g(r-(d[y][x]<`/`),d[y][x]=`/`):d.map(a=>a.join``).join`
`)=>i=setInterval(_=>o.data=f--?g(r,d=[...Array(9)].map(_=>[...` `.repeat(78)])):`

`+` `.repeat(40-m.length/2,clearInterval(i))+m,d*1e3)
```

```
<input id=f size=10 placeholder="# of frames"><input id=d placeholder="Interval between frames"><input id=r size=10 placeholder="# of raindrops"><input id=m placeholder="End message"><input type=button value=Go onclick=t(o.firstChild,+f.value,+d.value,+r.value,m.value)><pre id=o>
```

At least on my browser, the output is designed to fit into the Stack Snippet area without having to go "Full page", so if you ask for more than 702 raindrops it will crash.

Edit: Saved 7 bytes by using a text node as my output area.
> 10 votes

# Answer
## R, 196 192 185 bytes

Just a mock version I wrote based on the description. Hopefully it's somewhat what OP was looking for.

Saved some bytes thanks to @plannapus.

```
f=function(w,t,m,n){for(i in 1:t){x=matrix(" ",100,23);x[sample(2300,n)]="/";cat("\f",rbind(x,"\n"),sep="");Sys.sleep(w)};cat("\f",g<-rep("\n",11),rep(" ",(100-nchar(m))/2),m,g,sep="")}

```

The arguments:

* `w`: Wait time between frames
* `t`: Total number of frames
* `m`: Custom message
* `n`: Number of rain drops

**Example**

Why does it look like it's raining upwards?

Edit: I should mention that this is my customized 23x100 character R-studio console. The dimensions are hardcoded into the function but one could in principle use `getOption("width")` to make it flexible to console size.

**Ungolfed and explained**

```
f=function(w,t,m,n){
    for(i in 1:t){
        x=matrix(" ",100,23);             # Initialize matrix of console size
        x[sample(2300,n)]="/";            # Insert t randomly sampled "/"
        cat("\f",rbind(x,"\n"),sep="");   # Add newlines and print one frame
        Sys.sleep(w)                      # Sleep
    };
    cat("\f",g<-rep("\n",11),rep(" ",(100-nchar(m))/2),m,g,sep="")  # Print centered msg
}

```
> 8 votes

# Answer
## C 160 bytes

```
f(v,d,w,char *s){i,j;char c='/';for(i=0;i<v;i++){for(j=0;j<d;j++)printf("%*c",(rand()%100),c);fflush(stdout);sleep(w);}system("clear");printf("%*s\n",1000,s);}

v-Time the raindrops are visible in seconds.
d-Number of drops per iteration
w-Wait time in seconds, before the next iteration
s-String to be passed on once its done

```

Ungolfed version:

```
void f(int v, int d, int w,char *s)
{

   char c='/';
   for(int i=0;i<v;i++)
   {
      for(int j=0;j<d;j++)
         printf("%*c",(rand()%100),c);

      fflush(stdout);
      sleep(w);
   }
   system("clear");
   printf("%*s\n", 1000,s);
}

```

```
v - 5 seconds
d - 100 drops
w - 1 second wait time
s - "Raining Blood" :)

```
> 5 votes

# Answer
# R, 163 chars

```
f=function(w,t,n,m){for(i in 1:t){cat("\f",sample(rep(c("/"," "),c(n,1920-n))),sep="");Sys.sleep(w)};cat("\f",g<-rep("\n",12),rep(" ",(80-nchar(m))/2),m,g,sep="")}

```

With indents and newlines:

```
f=function(w,t,n,m){
    for(i in 1:t){
        cat("\f",sample(rep(c("/"," "),c(n,1920-n))),sep="")
        Sys.sleep(w)
    }
    cat("\f",g<-rep("\n",12),rep(" ",(80-nchar(m))/2),m,g,sep="")
}

```

It's adapted to a terminal size of 24 lines by 80 columns. `w` is the waiting time, `t` the number of frames, `n` the number of raindrops and `m` the final message.

It differs from @billywob's answer in the different use of `sample`: if the output size is omitted, `sample` gives a permutation of the input vector (here a vector containing the needed number of raindrops and the corresponding number of spaces, thanks to the fact that argument `times` of function `rep` is vectorized). As the size of the vector corresponds exactly to the size of the screen, there is no need to add newlines, or to force-shape it into a matrix.
> 4 votes

# Answer
# NodeJS: 691 158 148 Bytes

## Edit

As requested, additional features removed and golf'd.

```
s=[];setInterval(()=>{s=s.slice(L='',9);for(;!L[30];)L+=' |'[Math.random()*10&1];s.unshift(L);console.log("\u001b[2J\u001b[0;0H"+s.join('\n'))},99)

```

The rules specify disregard for size, but this version includes a glitch for the first few frames. It is **129 bytes.**

```
s='';setInterval(()=>{for(s='\n'+s.slice(0,290);!s[300];)s=' |'[Math.random()*10&1]+s;console.log("\u001b[2J\u001b[0;0H"+s)},99)

```

---

**Previous answer**

Perhaps not the best golfing, but I got a bit carried away. It has optional wind direction and rain factor.

`node rain.js 0 0.3`

```
var H=process.stdout.rows-2, W=process.stdout.columns,wnd=(arg=process.argv)[2]||0, rf=arg[3]||0.3, s=[];
let clr=()=>{ console.log("\u001b[2J\u001b[0;0H") }
let nc=()=>{ return ~~(Math.random()*1+rf) }
let nl=()=>{ L=[];for(i=0;i<W;i++)L.push(nc()); return L}
let itrl=(l)=>{ for(w=0;w<wnd;w++){l.pop();l.unshift(nc())}for(w=0;w>wnd;w--){l.shift();l.push(nc())};return l }
let itrs=()=>{ if(s.length>H)s.pop();s.unshift(nl());s.map(v=>itrl(v)) }
let d=(c,i)=>{if(!c)return ' ';if(i==H)return '*';if(wnd<0)return '/';if(wnd>0)return '\\';return '|'}
let drw=(s)=>{ console.log(s.map((v,i)=>{ return v.map(  c=>d(c,i)  ).join('') }).join('\r\n')) }
setInterval(()=>{itrs();clr();drw(s)},100)

```

See webm of it working here
> 3 votes

# Answer
# Ruby + GNU Core Utils, 169 bytes

Parameters to the function are wait time, number of iterations, message, and number of raindrops, in that order. Newlines for readability.

Core Utils were needed for `tput` and `clear`.

```
->w,t,m,n{x=`tput cols`.to_i;z=x*h=`tput lines`.to_i
t.times{s=' '*z;[*0...z].sample(n).map{|i|s[i]=?/};puts`clear`+s;sleep w}
puts`clear`+$/*(h/2),' '*(x/2-m.size/2)+m}

```
> 2 votes

# Answer
# Noodel, noncompeting 44 bytes

I had centering text on my list of things to do since I made the language... But, I was lazy and did not add until after this challenge. So, here I am not competing, but had fun with the challenge:)

```
ØGQÆ×Øæ3/×Æ3I_ȥ⁻¤×⁺Æ1Ḷḋŀ÷25¶İÇæḍ€Æ1uụC¶×12⁺ß

```

The console is size is hard coded to 25x50 which does not look good in the online editor, but does for the snippet.

Try it:)

---

### How It Works

```
Ø                                            # Pushes all of the inputs from the stack directly back into the stdin since it is the first token.

 GQÆ×Ø                                       # Turns the seconds into milliseconds since can only delay by milliseconds.
 GQ                                          # Pushes on the string "GQ" onto the top of the stack.
   Æ                                         # Consumes from stdin the value in the front and pushes it onto the stack which is the number of seconds to delay.
    ×                                        # Multiplies the two items on top of the stack.
                                             # Since the top of the stack is a number, the second parameter will be converted into a number. But, this will fail for the string "GQ" therein treated as a base 98 number producing 1000.
     Ø                                       # Pops off the new value, and pushes it into the front of stdin.

      æ3/×Æ3I_ȥ⁻¤×⁺                          # Creates the correct amount of rain drops and spaces to be displayed in a 50x25 console.
      æ3                                     # Copies the forth parameter (the number of rain drops).
        /                                    # Pushes the character "/" as the rain drop character.
         ×                                   # Repeats the rain drop character the specified number of times provided.
          Æ3                                 # Consumes the number of rain drops from stdin.
            I_                               # Pushes the string "I_" onto the stack.
              ȥ                              # Converts the string into a number as if it were a base 98 number producing 25 * 50 = 1250.
               ⁻                             # Subtract 1250 - [number rain drops] to get the number of spaces.
                ¤                            # Pushes on the string "¤" which for Noodel is a space.
                 ×                           # Replicate the "¤" that number of times.
                  ⁺                          # Concatenate the spaces with the rain drops.

                   Æ1Ḷḋŀ÷25¬İÇæḍ€            # Handles the animation of the rain drops.
                   Æ1                        # Consumes and pushes on the number of times to loop the animation.
                     Ḷ                       # Pops off the number of times to loop and loops the following code that many times.
                      ḋ                      # Duplicate the string with the rain drops and spaces.
                       ŀ                     # Shuffle the string using Fisher-Yates algorithm.
                        ÷25                  # Divide it into 25 equal parts and push on an array containing those parts.
                           ¶                 # Pushes on the string "¶" which is a new line.
                            İ                # Join the array by the given character.
                             Ç               # Clear the screen and display the rain.
                              æ              # Copy what is on the front of stdin onto the stack which is the number of milliseconds to delay.
                               ḍ             # Delay for the specified number of milliseconds.
                                €            # End of the loop.

                                 Æ1uụC¶×12⁺ß # Creates the centered text that is displayed at the end.
                                 Æ1          # Pushes on the final output string.
                                   u         # Pushes on the string "u" onto the top.
                                    ụC       # Convert the string on the top of the stack to an integer (which will fail and default to base 98 which is 50) then center the input string based off of that width.
                                      ¶      # Push on a the string "¶" which is a new line.
                                       ×12   # Repeat it 12 times.
                                          ⁺  # Append the input string that has been centered to the new lines.
                                           ß # Clear the screen.
                                             # Implicitly push on what is on the top of the stack which is the final output.

```

---

```
<div id="noodel" code="ØGQÆ×Øæ3/×Æ3I_ȥ⁻¤×⁺Æ1Ḷḋŀ÷25¶İÇæḍ€Æ1uụC¶×12⁺ß" input='0.2, 50, "Game Over", 30' cols="50" rows="25"></div>

<script src="https://tkellehe.github.io/noodel/noodel-latest.js"></script>
<script src="https://tkellehe.github.io/noodel/ppcg.min.js"></script>
```
> 2 votes

# Answer
# Python 2.7, ~~254~~ 251 bytes

This is my own try without using ncurses.

```
from time import*;from random import*;u=range;y=randint
def m(t,m,w,n):
    for _ in u(t):
        r=[[' 'for _ in u(40)]for _ in u(40)]
        for i in u(n):r[y(0,39)][y(0,39)]='/'
        print'\n'.join(map(lambda k:' '.join(k),r));sleep(w);print '<esc>[2J'
    print' '*33+m

```

Thank to @ErikTheOutgolfer for correcting and saving me bytes.
> 1 votes

# Answer
# SmileBASIC, 114 bytes

```
INPUT W,T,M$,N
FOR I=1TO T
VSYNC W*60CLS
FOR J=1TO N
LOCATE RND(50),RND(30)?7;
NEXT
NEXT
LOCATE 25-LEN(M$)/2,15?M$

```

Console size is always 50\*30.
> 1 votes

# Answer
## Perl 5, 156 bytes

**154 bytes code + 2 for `-pl`.**

```
$M=$_;$W=<>;$I=<>;$R=<>;$_=$"x8e3;{eval'$-=rand 8e3;s!.{$-}\K !/!;'x$R;print;select$a,$a,$a,$W;y!/! !;--$I&&redo}$-=3920-($l=length$M)/2;s;.{$-}\K.{$l};$M

```

Uses a fixed size of 160x50.

See it online!

---

## Perl 5, 203 bytes

**201 bytes code + 2 for `-pl`.**

```
$M=$_;$W=<>;$I=<>;$R=<>;$_=$"x($z=($x=`tput cols`)*($y=`tput lines`));{eval'$-=rand$z;s!.{$-}\K !/!;'x$R;print;select$a,$a,$a,$W;y!/! !;--$I&&redo}$-=$x*($y+!($y%2))/2-($l=length$M)/2;s;.{$-}\K.{$l};$M

```

Uses `tput` to determine the size of the terminal.
> 1 votes

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


title: Selling electricity

text:
# Question
Title: Selling electricity
Jack is a little businessman. He found out a way to earn money by buying electricity on days when it's cheap and selling it when it's much more expensive. He stores the electricity in a battery he made by himself.

### Challenge

You are given `N` (if required), the number of days Jack knows the cost of electricity for, and `X`, the amount of money Jack has available to invest in electricity, and the value(buy/sell value) of the electricity for `N` days. Your job is to determine when Jack should buy and when he should sell electricity in order to earn as much money as possible and simply print the largest possible sum of money he could have afterwards.

The value of the electricity is always a positive integer but depending on the amount of money Jack has, the amount of electricity and money he has may be floating point numbers.

### Examples

(I/O need not be exactly as shown):

1.

```
4 10
4 10 5 20

```

Output: `100`
\- because he buys electricity on the 1st day and the sells it on the 2nd and buys it on the 3rd and sells it on the 4th day.

2.

```
3 21
10 8 3

```

Output: `21`
\- because it's better if he doesn't buy/sell any electricity.

3.

```
3 10
8 10 14

```

Output: `17.5`
\- because he buys electricity on the 1st day, but he sells it on the 3rd day.

4.

```
5 10
4 2 10 5 20

```

Output: `200`
\- much like example 1, but this time Jack waits for the price to drop to `2` before making a purchase.

---

The program with the shortest amount of code wins! This is a code golf problem. Note:You can shorten the input, as long as it still makes sense.

# Answer
> 1 votes
# Husk, 7 bytes

```
Π:mY1Ẋ/

```

Try it online!

### How?

```
Π:mY1Ẋ/ – Full program.
     Ẋ  – For each pair of adjacent elements from the input list...
      / – ... Divide the second by the first.
  m     – For each quotient...
   Y1   – ... Get the maximum between it and 1.
 :      – Append the second input.
Π       – Get the product of the resulting list.

```

# Answer
> 5 votes
# Jelly,  ~~8~~  7 bytes

-1 byte thanks to Mr. Xcoder (use the `Ɲ` quick which performs `2\`)

```
÷@Ɲ»1P×

```

A dyadic link taking a list of the prices on the left and the initial capital on the right which returns the maximal capital.

**Try it online!** or see the test-suite.

### How?

Jack can sell every day on which the preceding day had a lower price and buy on those days (even if it is one on which he sold). When he does so his capital increases by `priceToday ÷ priceYesterday`, such gains multiply his initial capital, while any time the price falls he may simply forego the loss and multiply his capital by `1` instead by not transacting.

```
÷@Ɲ»1P× - Link: list, prices; number, initial capital  e.g. [4,2,10,5,20], 10
  Ɲ     - pairwise overlapping reduce left (prices) by:
÷@      -   division with swapped arguments                 [0.5,5,0.5,4]
    1   - literal one                                       1
   »    - maximum (vectorises)                              [1,5,1,4]
     P  - product                                           20
      × - multiply by right (initial capital)               200

```

# Answer
> 2 votes
# Coconut, ~~51~~ 45 bytes

thanks to @totallyhuman for -5 bytes

```
d->m->reduce((*),map(max$(1)..(/),d[1:],d))*m

```

Try it online!

Uses Jonathan Allan's algorithm.

Coconut extends Python with several functional programming constructs.

```
d->m->                      lambda function taking two arguments, money and prices, in currying syntax

    reduce((*),              product of...
           map(               map
               max$(1)..(/),   (x,y)->max(1, x/y)
                              over
               d[1:],d         consecutive pairs of prices
               )
          )*m                multiply with the initial money

```

# Answer
> 2 votes
# Haskell, 41 bytes

```
l#n=foldr((*).max 1)n$zipWith(/)(tail l)l

```

Try it online!

# Answer
> 1 votes
# Perl, 37 bytes

Includes `+4` for `-ap`

On STDIN first give a line with the list of prices, then a line with the starting capital

`electricity.pl`:

```
#!/usr/bin/perl -ap
$\=<>;s%\d+%$\*=$&>$'||$'/$&%eg}{

```

You can then for example run it as:

```
(echo 4 2 10 5 20; echo 10) | electricity.pl; echo

```

# Answer
> 1 votes
# 05AB1E, 9 bytes

```
Rü/εXM}P*

```

Try it online!

Uses the same method as in Jonathan Allan's Jelly answer

**Explanation**

```
R           # reverse input list of buy/sell values
 ü/         # pairwise division
   εXM}     # max of each element and 1
       P    # product
        *   # multiply by initial capital

```

# Answer
> 1 votes
# Stax, ~~21~~ 20 bytes

```
àq'4¢<╪╦ÉdεÖ!≤♠┬☻∟In

```

Run it

This is the ascii representation of the same program:

```
c|)s\Dc{|Mms{hm\{E:_m:**

```

I'm sure there is room for golfing here, but I wanted to give Stax a spin. Here's the breakdown.

```
                            Input stack: initial funds, array of prices
c                           Copy the array of prices
 |)                         Rotate the top copy one place right
   s                        Swap the two arrays on the main stack
    \                       Zip the arrays to get consecutive price pairs
     D                      Drop the first pair (don't need [price N, price 1])
      c                     Copy the result
       {|Mm                 Map max: Keep only the max of each pair (copy 1)
           s                Swap copy 1 and copy 2 on the main stack
            {hm             Map first: Keep only the first of each pair (copy 2)
               \            Zip copy 1 and copy 2
                {E:_m       Map explode, divide: Transform pairs with float division
                     :*     Array product: Multiply all resulting quotients
                       *    Multiply by other input (initial funds)

```

# Answer
> 0 votes
# Ruby, 57 bytes

```
->a,x{x*a.each_cons(2).map{|t|t.max*1.0/t[0]}.reduce(:*)}

```

Try it online!

A lambda taking an array of prices `a` and the starting capital `x`. The most interesting thing I found here is that it's faster to treat the pairs of prices as a tuple `t`, whereas my first instinct was `.map{|n,m|[m,n].max*1.0/m}`.

```
->a,x{
  x *                       # Multiply the starting capital by...
  a.each_cons(2).map{ |t|   # For each consecutive pair of prices
    t.max*1.0 / t[0]        # The larger of that pair, divided by the first
  }.reduce(:*)              # All multiplied together
}

```

---
Tags: code-golf, array, floating-point
---


title: Maximum run between identical elements

text:
# Question
Title: Maximum run between identical elements
> This is a overhaul of this now deleted question by ar kang. If the OP of that question would like to reclaim this question or has a problem with me posting this I'd be happy to accommodate

Given a list of integers as input find the maximum possible sum of a continuous sublist that starts and ends with the same value. The sublists must be of length at least 2. For example for the list

```
[1, 2, -2, 4, 1, 4]

```

There are 2 different continuous sublists start and end with the same value

```
[1,2,-2,4,1] -> 6
[4,1,4]      -> 9

```

The bigger sum is 9 so you output 9.

You may assume every input contains at least 1 duplicate.

This is so answers will be scored in bytes with fewer bytes being better.

## Test cases

```
[1,2,-2,4,1,4]  -> 9
[1,2,1,2]       -> 5
[-1,-2,-1,-2]   -> -4
[1,1,1,8,-1,8]  -> 15
[1,1,1,-1,6,-1] -> 4
[2,8,2,-3,2]    -> 12
[1,1,80]        -> 2
[2,8,2,3,2]     -> 17

```

# Answer
# Haskell, 62 bytes

`f` takes a list of integers and returns an integer.

```
f l=maximum[x+sum m-sum n|x:m<-t l,y:n<-t m,x==y]
t=scanr(:)[]

```

Try it online!

# How it works

* `t` is the standard "get all suffixes of a list without importing `Data.List.tails`" function.
* In `f l`, the list comprehension iterates through all the non-empty suffixes of the argument list `l`, with first element `x` and remainder `m`.
* For each, it does the same for all nonempty suffixes of `m`, selecting first element `y` and remainder `n`.
* If `x` and `y` are equal, the list comprehension includes the sum of the elements between them. This sublist is the same as `x:m` with its suffix `n` stripped off, so the sum can be calculated as `x+sum m-sum n`.
> 9 votes

# Answer
# JavaScript (ES6), ~~68~~ 62 bytes

```
a=>a.map(m=(x,i)=>a.map((y,j)=>m=j<=i||(x+=y)<m|y-a[i]?m:x))|m

```

### Test cases

```
let f =

a=>a.map(m=(x,i)=>a.map((y,j)=>m=j<=i||(x+=y)<m|y-a[i]?m:x))|m

console.log(f([1,2,-2,4,1,4] )) // -> 9
console.log(f([1,2,1,2]      )) // -> 5
console.log(f([-1,-2,-1,-2]  )) // -> -4
console.log(f([1,1,1,8,-1,8] )) // -> 15
console.log(f([1,1,1,-1,6,-1])) // -> 4
console.log(f([2,8,2,-3,2]   )) // -> 12
console.log(f([1,1,80]       )) // -> 2
```

### Commented

```
a =>                    // a = input array
  a.map(m =             // initialize m to a function (gives NaN in arithmetic operations)
    (x, i) =>           // for each entry x at position i in a:
    a.map((y, j) =>     //   for each entry y at position j in a:
      m =               //     update m:
        j <= i ||       //       if j is not after i
        (x += y) < m |  //       or the sum x, once updated, is less than m
        y - a[i] ?      //       or the current entry is not equal to the reference entry:
          m             //         let m unchanged
        :               //       else:
          x             //         update m to the current sum
    )                   //   end of inner map()
  ) | m                 // end of outer map(); return m

```
> 8 votes

# Answer
# Jelly, 12 bytes

```
ĠŒc€Ẏr/€ịḅ1Ṁ

```

Try it online!

### How it works

```
ĠŒc€Ẏr/€ịḅ1Ṁ  Main link. Argument: A (array)

Ġ             Group the indices of A by their corresponding values.
 Œc€          Take all 2-combinations of grouped indices.
    Ẏ         Dumps all pairs into a single array.
     r/€      Reduce each pair by range, mapping [i, j] to [i, ..., j].
        ị     Index into A.
         ḅ1   Convert each resulting vector from base 1 to integer, effectively
              summing its coordinates.
           Ṁ  Take the maximum.

```
> 5 votes

# Answer
# Husk, 10 bytes

```
▲mΣfΓ~€;ṫQ

```

Try it online!

## Explanation

```
▲mΣfΓ~€;ṫQ  Input is a list, say x=[1,2,-2,4,1,4]
         Q  Slices: [[1],[2],[1,2],..,[1,2,-2,4,1,4]]
   f        Keep those that satisfy this:
    Γ        Deconstruct into head and tail, for example h=2 and t=[-2,4,1]
        ;    Wrap h: [2]
      ~€     Is it an element of
         ṫ   Tails of t: [[-2,4,1],[4,1],[1]]
            Result: [[1,2,-2,4,1],[4,1,4]]
 mΣ         Map sum: [6,9]
▲           Maximum: 9

```
> 5 votes

# Answer
# , ~~108~~ ~~103~~ ~~90~~ ~~88~~ 83 bytes

```
function(l)max(combn(seq(l),2,function(x)"if"(rev(p<-l[x[1]:x[2]])-p,-Inf,sum(p))))

```

Try it online!

`combn` strikes again! Generates all sublists of length at least `2`, sets the sublist sum to `-Inf` if the first and last are not equal, and takes the max of all the sums.

The `"if"` will raise a bunch of warnings but they are safely ignorable -- that's probably the best golfing trick here, `rev(p)-p` is zero in the first element iff `p[1]==tail(p,1)`, and `"if"` uses the first element of its condition with a warning.
> 3 votes

# Answer
# Haskell, 66 bytes

```
maximum.f
f(x:y)=[sum$x:take a y|(a,b)<-zip[1..]y,b==x]++f y
f x=x

```

Try it online!
> 3 votes

# Answer
# Python 3, 81 bytes

```
lambda x,e=enumerate:max(sum(x[i:j+1])for i,a in e(x)for j,b in e(x)if(a==b)*j>i)

```

Try it online!
> 3 votes

# Answer
# Python, 62 bytes

```
f=lambda l:l and max(f(l[1:]),[sum(l)]*(l.pop()in l[:1]),f(l))

```

Try it online!

Outputs a singleton list.
> 3 votes

# Answer
# Jelly, ~~13~~, 12 bytes

```
=ṚṖḢ
ẆÇÐfS€Ṁ

```

Try it online!

One byte saved by Mr. Xcoder, who is currently competing with me. :D

Explanation:

```
        # Helper link:
=Ṛ      # Compare each element of the list to the element on the opposite side (comparing the first and last)
  Ṗ     # Pop the last element of the resulting list (so that single elements return falsy)
   Ḣ    # Return the first element of this list (1 if the first and last are equal, 0 otherwise)

        # Main link:
Ẇ       # Return every sublist
 Ç      # Where the helper link
  Ðf    # Returns true (1)
    S€  # Sum each resulting list
      Ṁ # Return the max

```
> 2 votes

# Answer
## Wolfram Language (Mathematica), 54 bytes

```
Max@SequenceCases[#,{a_,b___,a_}:>2a+b,Overlaps->All]&

```

Try it online!
> 2 votes

# Answer
# Jelly, 11 bytes

Uses some features that post-date the challenge.

```
Ẇµ.ịEȧḊµƇ§Ṁ

```

Try it online!

### How it works?

```
Ẇµ.ịEȧḊµƇ§Ṁ  || Full program. Takes input from CLA, outputs to STDOUT.
Ẇ            || Sublists.
 µ     µƇ    || Filter-Keep those
    ȧḊ       || ... Which have length at least 2 and ...
 .ị          || ... The elements at floor(0.5) and ceil(0.5) (modular, 1-indexed) ...
    E        || ... Are equal.
         §   || Sum each.
          Ṁ  || Maximum.

```

-1 with help from caird.
> 1 votes

# Answer
# Python 2, 86 bytes

*Outgolfed by Dennis*

```
lambda x:max(sum(x[i:j+1])for i,v in enumerate(x)for j in range(i+1,len(x))if v==x[j])

```

Try it online!

Generates all sublists larger than length 2, where the first element is equal to the last, then maps each to its sum and selects the largest value.
> 1 votes

# Answer
# Pyth, 15 bytes

```
eSsMf&qhTeTtT.:

```

Try it online

### Explanation

```
eSsMf&qhTeTtT.:
             .:Q  Take all sublists of the (implicit) input.
    f qhTeT       Take the ones that start and end with the same number...
     &     tT     ... and have length at least 2.
  sM              Take the sum of each.
eS                Get the largest.

```
> 1 votes

# Answer
# 05AB1E, 9 bytes

```
ŒʒćsθQ}OZ

```

Try it online!

**Explanation**

```
Œ          # push sublists of input
 ʒ    }    # filter, keep values where
  ć        # the head of the list, extracted
     Q     # is equal to
   sθ      # the last element of the rest of the list
       O   # sum the resulting sublists
        Z  # get the max

```
> 1 votes

# Answer
# Clean, ~~94~~ ~~90~~ 86 bytes

```
import StdEnv,StdLib
@l=last(sort[sum(l%(i,j))\\e<-l&i<-[0..],j<-elemIndices e l|j>i])

```

Try it online!
> 1 votes

# Answer
# Ruby, 64 bytes

```
->l{w,*r=0;(z=l.index w)&&r<<w+l[z..-1].sum while w=l.pop;r.max}

```

Try it online!
> 1 votes

# Answer
# Julia 0.6, 70 bytes

```
a->maximum(sum(a[i:k]) for b=[findin(a,x) for x=a] for i=b,k=b if k>i)

```

Try it online!
> 1 votes

# Answer
# C, 104 bytes

```
i,j,s,l;f(a,n)int*a;{for(i=0,l=1<<31;i<n;++i)for(s=a[j=i];++j<n;l=a[j]-a[i]?l:s>l?s:l)s+=a[j];return l;}

```

Try it online!

# C (gcc), 99 bytes

```
i,j,s,l;f(a,n)int*a;{for(i=0,l=1<<31;i<n;++i)for(s=a[j=i];++j<n;l=a[j]-a[i]?l:s>l?s:l)s+=a[j];l=l;}

```

Try it online!
> 0 votes

# Answer
## Batch, 179 bytes

```
@set s=%*
@set/a"m=-1<<30
:l
@set/at=n=%s: =,%
@set s=%s:* =%
@for %%e in (%s%)do @set/at+=%%e&if %%e==%n% set/a"m+=(m-t)*(m-t>>31)
@if not "%s%"=="%s: =%" goto l
@echo %m%

```

Takes input as command-line parameters.
> 0 votes

# Answer
## Clojure, 92 bytes

```
#(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))

```
> 0 votes

# Answer
## Java 8, 129 byes

```
a->a.stream().map(b->a.subList(a.indexOf(b),a.lastIndexOf(b)+1).stream().mapToLong(Long::intValue).sum()).reduce(Long::max).get()

```

For each integer `X` in the list, the function finds the sum of the largest sublist with start and end `X`. Then, it finds the maximum sum as the OP specifies.
> 0 votes

# Answer
# Perl, ~~61~~ 59 bytes

Includes `+3` for `-p`:

`max_ident_run.pl`:

```
#!/usr/bin/perl -p
s:\S+:$%=$&;($%+=$_)<($\//$%)||$_-$&or$\=$%for<$' >:eg}{

```

Run as:

```
max_ident_run.pl <<< "1 2 -2 4 1 4 1"

```
> 0 votes

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