title: Shortest universal maze exit string

text:
# Question
Title: Shortest universal maze exit string
A maze on an N by N grid of square cells is defined by specifying whether each edge is a wall or not a wall. All outer edges are walls. One cell is defined as the ***start***, and one cell is defined as the ***exit***, and the exit is reachable from the start. The start and exit are never the same cell.

Note that neither the start nor the exit need to be on the outer border of the maze, so this is a valid maze:

A string of 'N', 'E', 'S' and 'W' indicates attempting to move North, East, South and West respectively. A move that is blocked by a wall is skipped without movement. A string ***exits*** a maze if applying that string from the start results in the exit being reached (regardless of whether the string continues after reaching the exit).

Inspired by this puzzling.SE question for which xnor provided a provable method of solving with a *very* long string, write code that can find a single string that exits any 3 by 3 maze.

*Excluding invalid mazes (start and exit on the same cell, or exit not reachable from start) there are 138,172 valid mazes and the string must exit each of them.*

### Validity

The string must satisfy the following:

* It is composed of only the characters 'N', 'E', 'S' and 'W'.
* It exits any maze it is applied to, if started at the start.

Since the set of all possible mazes includes each possible maze with each possible valid starting point, this automatically means that the string will exit any maze from *any* valid starting point. That is, from any starting point from which the exit is reachable.

### Winning

The winner is the answer that provides the shortest valid string and includes the code used to produce it. If more than one of the answers provide a string of this shortest length, the first to post that string length wins.

### Example

Here is an example string 500 characters long, to give you something to beat:

```
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE

```

*Thanks to orlp for donating this.*

---

### Leaderboard

*Equal scores are listed in order of posting of that score. This is not necessarily the order that the answers were posted since the score for a given answer may be updated over time.*

---

# Judge

Here is a Python 3 validator that takes a string of NESW as a command line argument or via STDIN.

For an invalid string, this will give you a visual example of a maze it fails for.

# Answer
# C++, 97 95 93 91 86 83 82 81 79 characters

> NNWSWNNSENESESWSSWNSEENWWNWSSEWWNENWEENWSWNWSSENENWNWNESENESESWNWSESEWWNENWNEES

My strategy is fairly simple - an evolution algorithm that can grow, shrink, swap elements of and mutate valid sequences. My evolution logic is now nearly the same as @Sp3000's, as his was an improvement over mine.

However, my implementation of the maze logic is rather nifty. This allows me to check if strings are valid at blistering speed. Try to figure it out by looking at the comment, `do_move` and the `Maze` constructor.

```
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <vector>

/*
    Positions:

        8, 10, 12
        16, 18, 20
        24, 26, 28

    By defining as enum respectively N, W, E, S as 0, 1, 2, 3 we get:

        N: -8, E: 2, S: 8, W: -2
        0: -8, 1: -2, 2: 2, 3: 8

    To get the indices for the walls, average the numbers of the positions it
    would be blocking. This gives the following indices:

        9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27

    We'll construct a wall mask with a 1 bit for every position that does not
    have a wall. Then if a 1 shifted by the average of the positions AND'd with
    the wall mask is zero, we have hit a wall.
*/

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, W, E, S };

int do_move(uint32_t walls, int pos, int move) {
    int idx = pos + move / 2;
    return walls & (1ull << idx) ? pos + move : pos;
}

struct Maze {
    uint32_t walls;
    int start, end;

    Maze(uint32_t maze_id, int start, int end) {
        walls = 0;
        for (int i = 0; i < 12; ++i) {
            if (maze_id & (1 << i)) walls |= 1 << wall_idx[i];
        }
        this->start = encoded_pos[start];
        this->end = encoded_pos[end];
    }

    uint32_t reachable() {
        if (start == end) return false;

        uint32_t reached = 0;
        std::vector<int> fill; fill.reserve(8); fill.push_back(start);
        while (fill.size()) {
            int pos = fill.back(); fill.pop_back();
            if (reached & (1 << pos)) continue;
            reached |= 1 << pos;
            for (int m : move_offsets) fill.push_back(do_move(walls, pos, m));
        }

        return reached;
    }

    bool interesting() {
        uint32_t reached = reachable();
        if (!(reached & (1 << end))) return false;
        if (std::bitset<32>(reached).count() <= 4) return false;

        int max_deg = 0;
        uint32_t ends = 0;
        for (int p = 0; p < 9; ++p) {
            int pos = encoded_pos[p];
            if (reached & (1 << pos)) {
                int deg = 0;
                for (int m : move_offsets) {
                    if (pos != do_move(walls, pos, m)) ++deg;
                }
                if (deg == 1) ends |= 1 << pos;
                max_deg = std::max(deg, max_deg);
            }
        }

        if (max_deg <= 2 && ends != ((1u << start) | (1u << end))) return false;

        return true;
    }
};

std::vector<Maze> gen_valid_mazes() {
    std::vector<Maze> mazes;
    for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
        for (int points = 0; points < 9*9; ++points) {
            Maze maze(maze_id, points % 9, points / 9);
            if (!maze.interesting()) continue;
            mazes.push_back(maze);
        }
    }

    return mazes;
}

bool is_solution(const std::vector<int>& moves, Maze maze) {
    int pos = maze.start;
    for (auto move : moves) {
        pos = do_move(maze.walls, pos, move);
        if (pos == maze.end) return true;
    }

    return false;
}

std::vector<int> str_to_moves(std::string str) {
    std::vector<int> moves;
    for (auto c : str) {
        switch (c) {
        case 'N': moves.push_back(N); break;
        case 'E': moves.push_back(E); break;
        case 'S': moves.push_back(S); break;
        case 'W': moves.push_back(W); break;
        }
    }

    return moves;
}

std::string moves_to_str(const std::vector<int>& moves) {
    std::string result;
    for (auto move : moves) {
             if (move == N) result += "N";
        else if (move == E) result += "E";
        else if (move == S) result += "S";
        else if (move == W) result += "W";
    }
    return result;
}

bool solves_all(const std::vector<int>& moves, std::vector<Maze>& mazes) {
    for (size_t i = 0; i < mazes.size(); ++i) {
        if (!is_solution(moves, mazes[i])) {
            // Bring failing maze closer to begin.
            std::swap(mazes[i], mazes[i / 2]);
            return false;
        }
    }
    return true;
}

template<class Gen>
int randint(int lo, int hi, Gen& gen) {
    return std::uniform_int_distribution<int>(lo, hi)(gen);
}

template<class Gen>
int randmove(Gen& gen) { return move_offsets[randint(0, 3, gen)]; }

constexpr double mutation_p = 0.35; // Chance to mutate.
constexpr double grow_p = 0.1; // Chance to grow.
constexpr double swap_p = 0.2; // Chance to swap.

int main(int argc, char** argv) {
    std::random_device rnd;
    std::mt19937 rng(rnd());
    std::uniform_real_distribution<double> real;
    std::exponential_distribution<double> exp_big(0.5);
    std::exponential_distribution<double> exp_small(2);

    std::vector<Maze> mazes = gen_valid_mazes();

    std::vector<int> moves;
    while (!solves_all(moves, mazes)) {
        moves.clear();
        for (int m = 0; m < 500; m++) moves.push_back(randmove(rng));
    }

    size_t best_seen = moves.size();
    std::set<std::vector<int>> printed;
    while (true) {
        std::vector<int> new_moves(moves);
        double p = real(rng);

        if (p < grow_p && moves.size() < best_seen + 10) {
            int idx = randint(0, new_moves.size() - 1, rng);
            new_moves.insert(new_moves.begin() + idx, randmove(rng));
        } else if (p < swap_p) {
            int num_swap = std::min<int>(1 + exp_big(rng), new_moves.size()/2);
            for (int i = 0; i < num_swap; ++i) {
                int a = randint(0, new_moves.size() - 1, rng);
                int b = randint(0, new_moves.size() - 1, rng);
                std::swap(new_moves[a], new_moves[b]);
            }
        } else if (p < mutation_p) {
            int num_mut = std::min<int>(1 + exp_big(rng), new_moves.size());
            for (int i = 0; i < num_mut; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves[idx] = randmove(rng);
            }
        } else {
            int num_shrink = std::min<int>(1 + exp_small(rng), new_moves.size());
            for (int i = 0; i < num_shrink; ++i) {
                int idx = randint(0, new_moves.size() - 1, rng);
                new_moves.erase(new_moves.begin() + idx);
            }
        }

        if (solves_all(new_moves, mazes)) {
            moves = new_moves;

            if (moves.size() <= best_seen && !printed.count(moves)) {
                std::cout << moves.size() << " " << moves_to_str(moves) << "\n";
                if (moves.size() < best_seen) {
                    printed.clear(); best_seen = moves.size();
                }
                printed.insert(moves);
            }
        }
    }

    return 0;
}

```
> 39 votes

# Answer
# Python 3 + PyPy, ~~82~~ 80 characters

```
SWWNNSENESESWSSWSEENWNWSWSEWNWNENENWWSESSEWSWNWSENWEENWWNNESENESSWNWSESESWWNNESE

```

I've been hesitant to post this answer because I've basically taken orlp's approach and put my own spin on it. This string was found by starting with a pseudorandom length 500 solution - quite a number of seeds were tried before I could break the current record.

The only new major optimisation is that I only look at one third of the mazes. Two categories of mazes are excluded from the search:

* Mazes where `<= 7` squares are reachable
* Mazes where all reachable squares are on a single path, and the start/finish are not at both ends

The idea is that any string which solves the rest of the mazes should also solve the above automatically. I'm convinced this is true for the second type, but it is definitely not true for the first, so the output will contain some false positives that need to be checked separately. These false positive usually only miss about 20 mazes though, so I thought it'd be a good tradeoff between speed and accuracy, and it would also give the strings a little more breathing space to mutate.

Initially I went through a long list of search heuristics, but horrifically none of them came up with anything better than 140 or so.

```
import random

N, M = 3, 3

W = 2*N-1
H = 2*M-1

random.seed(142857)

def move(c, cell, walls):
    global W, H

    if c == "N":
        if cell > W and not (1<<(cell-W)//2 & walls):
            cell = cell - W*2

    elif c == "S":
        if cell < W*(H-1) and not (1<<(cell+W)//2 & walls):
            cell = cell + W*2

    elif c == "E":
        if cell % W < W-1 and not (1<<(cell+1)//2 & walls):
            cell = cell + 2

    elif c == "W":
        if cell % W > 0 and not (1<<(cell-1)//2 & walls):
            cell = cell - 2

    return cell

def valid_maze(start, finish, walls):
    global adjacent

    if start == finish:
        return False

    visited = set()
    cells = [start]

    while cells:
        curr_cell = cells.pop()

        if curr_cell == finish:
            return True

        if curr_cell in visited:
            continue

        visited.add(curr_cell)

        for c in "NSEW":
            cells.append(move(c, curr_cell, walls))

    return False

def print_maze(maze):
    start, finish, walls = maze
    print_str = "".join(" #"[walls & (1 << i//2) != 0] if i%2 == 1
                        else " SF"[2*(i==finish) + (i==start)]
                        for i in range(W*H))

    print("#"*(H+2))

    for i in range(H):
        print("#" + print_str[i*W:(i+1)*W] + "#")

    print("#"*(H+2), end="\n\n")

all_cells = [W*y+x for y in range(0, H, 2) for x in range(0, W, 2)]
mazes = []

for start in all_cells:
    for finish in all_cells:
        for walls in range(1<<(N*(M-1) + M*(N-1))):
            if valid_maze(start, finish, walls):
                mazes.append((start, finish, walls))

num_mazes = len(mazes)
print(num_mazes, "mazes generated")

to_remove = set()

for i, maze in enumerate(mazes):
    start, finish, walls = maze

    reachable = set()
    cells = [start]

    while cells:
        cell = cells.pop()

        if cell in reachable:
            continue

        reachable.add(cell)

        if cell == finish:
            continue

        for c in "NSEW":
            new_cell = move(c, cell, walls)
            cells.append(new_cell)

    max_deg = 0
    sf = set()

    for cell in reachable:
        deg = 0

        for c in "NSEW":
            if move(c, cell, walls) != cell:
                deg += 1

        max_deg = max(deg, max_deg)

        if deg == 1:
            sf.add(cell)

    if max_deg <= 2 and len(sf) == 2 and sf != {start, finish}:
        # Single path subset
        to_remove.add(i)

    elif len(reachable) <= (N*M*4)//5:
        # Low reachability maze, above ratio is adjustable
        to_remove.add(i)

mazes = [maze for i,maze in enumerate(mazes) if i not in to_remove]
print(num_mazes - len(mazes), "mazes removed,", len(mazes), "remaining")
num_mazes = len(mazes)

def check(string, cache = set()):
    global mazes

    if string in cache:
        return True

    for i, maze in enumerate(mazes):
        start, finish, walls = maze
        cell = start

        for c in string:
            cell = move(c, cell, walls)

            if cell == finish:
                break

        else:
            # Swap maze to front
            mazes[i//2], mazes[i] = mazes[i], mazes[i//2]
            return False

    cache.add(string)
    return True

while True:
    string = "".join(random.choice("NSEW") for _ in range(500))

    if check(string):
        break

# string = "NWWSSESNESESNNWNNSWNWSSENESWSWNENENWNWESESENNESWSESWNWSWNNEWSESWSEEWNENWWSSNNEESS"

best = len(string)
seen = set()

while True:
    action = random.random()

    if action < 0.1:
        # Grow
        num_grow = int(random.expovariate(lambd=3)) + 1
        new_string = string

        for _ in range(num_grow):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + random.choice("NSEW") + new_string[i:]

    elif action < 0.2:
        # Swap
        num_swap = int(random.expovariate(lambd=1)) + 1
        new_string = string

        for _ in range(num_swap):
            i,j = sorted(random.sample(range(len(new_string)), 2))
            new_string = new_string[:i] + new_string[j] + new_string[i+1:j] + new_string[i] + new_string[j+1:]

    elif action < 0.35:
        # Mutate
        num_mutate = int(random.expovariate(lambd=1)) + 1
        new_string = string

        for _ in range(num_mutate):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + random.choice("NSEW") + new_string[i+1:]

    else:
        # Shrink
        num_shrink = int(random.expovariate(lambd=3)) + 1
        new_string = string

        for _ in range(num_shrink):
            i = random.randrange(len(new_string))
            new_string = new_string[:i] + new_string[i+1:]

    if check(new_string):
        string = new_string

    if len(string) <= best and string not in seen:
        while True:
            if len(string) < best:
                seen = set()

            seen.add(string)
            best = len(string)
            print(string, len(string))

            # Force removals on new record strings
            for i in range(len(string)):
                new_string = string[:i] + string[i+1:]

                if check(new_string):
                    string = new_string
                    break

            else:
                break

```
> 18 votes

# Answer
# C++ and the library from lingeling

> Summary: A new approach, *no new solutions*, a nice program to play with, and some interesting results of local non-improvability of the known solutions. Oh, and some generally useful observations.

Using a SAT based approach, I could completely solve the similar problem for 4x4 mazes with blocked cells instead of thin walls and fixed start and exit positions at opposite corners. So I hoped to be able to use the same ideas for this problem. However, even though for the other problem I only used 2423 mazes (in the meantime it has been observed that 2083 are enough) and it has a solution of length 29, the SAT encoding used millions of variables and solving it took days.

So I decided to change the approach in two important ways:

* Don't insist on searching a solution from scratch, but allow to fix a part of the solution string. (That's easy to do anyway by adding unit clauses, but my program makes it comfortable to do.)
* Don't use all mazes from the beginning. Instead, incrementally add one unsolved maze at a time. Some mazes may be solved by chance, or they are always solved when the ones already considered are solved. In the latter case, it will never be added, without us needing to know the implication.

I also did some optimizations to use less variables and unit clauses.

The program is based on @orlp's. An important change was the selection of mazes:

* First of all, mazes are given by their wall structure and the start position only. (They also store the reachable positions.) The function `is_solution` checks if all reachable positions are reached.
* (Unchanged: still not using mazes with only 4 or less reachable positions. But most of them would be thrown away anyway by the following observations.)
* If a maze does not use any of the three top cells, it is equivalent to a maze that is shifted up. So we can drop it. Likewise for a maze that does not use any of the three left cells.
* It doesn't matter if unreachable parts are connected, so we insist that each unreachable cell is completely surrounded by walls.
* A single path maze that is a submaze of a bigger single path maze is always solved when the bigger one is solved, so we don't need it. Each single path maze of size at most 7 is part of a bigger one (still fitting in 3x3), but there are size 8 single path mazes that aren't. For simpliciy, let's just drop single path mazes of size less than 8. (And I'm still using that only the extreme points need to be considered as start positions. All positions are used as exit positions, which only matters for the SAT part of the program.)

In this way, I get a total of 10772 mazes with start positions.

Here is the program:

```
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
#include <limits>
#include <cassert>

extern "C"{
#include "lglib.h"
}

// reusing a lot of @orlp's ideas and code

enum { N = -8, W = -2, E = 2, S = 8 };
static const int encoded_pos[] = {8, 10, 12, 16, 18, 20, 24, 26, 28};
static const int wall_idx[] = {9, 11, 12, 14, 16, 17, 19, 20, 22, 24, 25, 27};
static const int move_offsets[] = { N, E, S, W };
static const uint32_t toppos = 1ull << 8 | 1ull << 10 | 1ull << 12;
static const uint32_t leftpos = 1ull << 8 | 1ull << 16 | 1ull << 24;
static const int unencoded_pos[] = {0,0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,3,
                                    0,4,0,5,0,0,0,6,0,7,0,8};

int do_move(uint32_t walls, int pos, int move) {
  int idx = pos + move / 2;
  return walls & (1ull << idx) ? pos + move : pos;
}

struct Maze {
  uint32_t walls, reach;
  int start;

  Maze(uint32_t walls=0, uint32_t reach=0, int start=0):
    walls(walls),reach(reach),start(start) {}

  bool is_dummy() const {
    return (walls==0);
  }

  std::size_t size() const{
    return std::bitset<32>(reach).count();
  }

  std::size_t simplicity() const{  // how many potential walls aren't there?
    return std::bitset<32>(walls).count();
  }

};

bool cmp(const Maze& a, const Maze& b){
  auto asz = a.size();
  auto bsz = b.size();
  if (asz>bsz) return true;
  if (asz<bsz) return false;
  return a.simplicity()<b.simplicity();
}

uint32_t reachable(uint32_t walls) {
  static int fill[9];
  uint32_t reached = 0;
  uint32_t reached_relevant = 0;
  for (int start : encoded_pos){
    if ((1ull << start) & reached) continue;
    uint32_t reached_component = (1ull << start);
    fill[0]=start;
    int count=1;
    for(int i=0; i<count; ++i)
      for(int m : move_offsets) {
        int newpos = do_move(walls, fill[i], m);
        if (reached_component & (1ull << newpos)) continue;
        reached_component |= 1ull << newpos;
        fill[count++] = newpos;
      }
    if (count>1){
      if (reached_relevant)
        return 0;  // more than one nonsingular component
      if (!(reached_component & toppos) || !(reached_component & leftpos))
        return 0;  // equivalent to shifted version
      if (std::bitset<32>(reached_component).count() <= 4)
        return 0;
      reached_relevant = reached_component;
    }
    reached |= reached_component;
  }
  return reached_relevant;
}

void enterMazes(uint32_t walls, uint32_t reached, std::vector<Maze>& mazes){
  int max_deg = 0;
  uint32_t ends = 0;
  for (int pos : encoded_pos)
    if (reached & (1ull << pos)) {
      int deg = 0;
      for (int m : move_offsets) {
        if (pos != do_move(walls, pos, m))
          ++deg;
      }
      if (deg == 1)
        ends |= 1ull << pos;
      max_deg = std::max(deg, max_deg);
    }
  uint32_t starts = reached;
  if (max_deg == 2){
    if (std::bitset<32>(reached).count() <= 7)
      return; // small paths are redundant
    starts = ends; // need only start at extremal points
  }
  for (int pos : encoded_pos)
    if ( starts & (1ull << pos))
      mazes.emplace_back(walls, reached, pos);
}

std::vector<Maze> gen_valid_mazes() {
  std::vector<Maze> mazes;
  for (int maze_id = 0; maze_id < (1 << 12); maze_id++) {
    uint32_t walls = 0;
    for (int i = 0; i < 12; ++i)
      if (maze_id & (1 << i))
    walls |= 1ull << wall_idx[i];
    uint32_t reached=reachable(walls);
    if (!reached) continue;
    enterMazes(walls, reached, mazes);
  }
  std::sort(mazes.begin(),mazes.end(),cmp);
  return mazes;
};

bool is_solution(const std::vector<int>& moves, Maze& maze) {
  int pos = maze.start;
  uint32_t reached = 1ull << pos;
  for (auto move : moves) {
    pos = do_move(maze.walls, pos, move);
    reached |= 1ull << pos;
    if (reached == maze.reach) return true;
  }
  return false;
}

std::vector<int> str_to_moves(std::string str) {
  std::vector<int> moves;
  for (auto c : str) {
    switch (c) {
    case 'N': moves.push_back(N); break;
    case 'E': moves.push_back(E); break;
    case 'S': moves.push_back(S); break;
    case 'W': moves.push_back(W); break;
    }
  }
  return moves;
}

Maze unsolved(const std::vector<int>& moves, std::vector<Maze>& mazes) {
  int unsolved_count = 0;
  Maze problem{};
  for (Maze m : mazes)
    if (!is_solution(moves, m))
      if(!(unsolved_count++))
    problem=m;
  if (unsolved_count)
    std::cout << "unsolved: " << unsolved_count << "\n";
  return problem;
}

LGL * lgl;

constexpr int TRUELIT = std::numeric_limits<int>::max();
constexpr int FALSELIT = -TRUELIT;

int new_var(){
  static int next_var = 1;
  assert(next_var<TRUELIT);
  return next_var++;
}

bool lit_is_true(int lit){
  int abslit = lit>0 ? lit : -lit;
  bool res = (abslit==TRUELIT) || (lglderef(lgl,abslit)>0);
  return lit>0 ? res : !res;
}

void unsat(){
  std::cout << "Unsatisfiable!\n";
  std::exit(1);
}

void clause(const std::set<int>& lits){
  if (lits.find(TRUELIT) != lits.end())
    return;
  for (int lit : lits)
    if (lits.find(-lit) != lits.end())
      return;
  int found=0;
  for (int lit : lits)
    if (lit != FALSELIT){
      lgladd(lgl, lit);
      found=1;
    }
  lgladd(lgl, 0);
  if (!found)
    unsat();
}

void at_most_one(const std::set<int>& lits){
  if (lits.size()<2)
    return;
  for(auto it1=lits.cbegin(); it1!=lits.cend(); ++it1){
    auto it2=it1;
    ++it2;
    for(  ; it2!=lits.cend(); ++it2)
      clause( {- *it1, - *it2} );
  }
}

/* Usually, lit_op(lits,sgn) creates a new variable which it returns,
   and adds clauses that ensure that the variable is equivalent to the
   disjunction (if sgn==1) or the conjunction (if sgn==-1) of the literals
   in lits. However, if this disjunction or conjunction is constant True
   or False or simplifies to a single literal, that is returned without
   creating a new variable and without adding clauses.                    */

int lit_op(std::set<int> lits, int sgn){
  if (lits.find(sgn*TRUELIT) != lits.end())
    return sgn*TRUELIT;
  lits.erase(sgn*FALSELIT);
  if (!lits.size())
    return sgn*FALSELIT;
  if (lits.size()==1)
    return *lits.begin();
  int res=new_var();
  for(int lit : lits)
    clause({sgn*res,-sgn*lit});
  for(int lit : lits)
    lgladd(lgl,sgn*lit);
  lgladd(lgl,-sgn*res);
  lgladd(lgl,0);
  return res;
}

int lit_or(std::set<int> lits){
  return lit_op(lits,1);
}

int lit_and(std::set<int> lits){
  return lit_op(lits,-1);
}

using A4 = std::array<int,4>;

void add_maze_conditions(Maze m, std::vector<A4> dirs, int len){
  int mp[9][2];
  int rp[9];
  for(int p=0; p<9; ++p)
    if((1ull << encoded_pos[p]) & m.reach)
      rp[p] = mp[p][0] = encoded_pos[p]==m.start ? TRUELIT : FALSELIT;
  int t=0;
  for(int i=0; i<len; ++i){
    std::set<int> posn {};
    for(int p=0; p<9; ++p){
      int ep = encoded_pos[p];
      if((1ull << ep) & m.reach){
        std::set<int> reach_pos {};
        for(int d=0; d<4; ++d){
          int np = do_move(m.walls, ep, move_offsets[d]);
          reach_pos.insert( lit_and({mp[unencoded_pos[np]][t],
                                  dirs[i][d ^ ((np==ep)?0:2)]    }));
        }
        int pl = lit_or(reach_pos);
        mp[p][!t] = pl;
        rp[p] = lit_or({rp[p], pl});
        posn.insert(pl);
      }
    }
    at_most_one(posn);
    t=!t;
  }
  for(int p=0; p<9; ++p)
    if((1ull << encoded_pos[p]) & m.reach)
      clause({rp[p]});
}

void usage(char* argv0){
  std::cout << "usage: " << argv0 <<
    " <string>\n   where <string> consists of 'N', 'E', 'S', 'W' and '*'.\n" ;
  std::exit(2);
}

const std::string nesw{"NESW"};

int main(int argc, char** argv) {
  if (argc!=2)
    usage(argv[0]);
  std::vector<Maze> mazes = gen_valid_mazes();
  std::cout << "Mazes with start positions: " << mazes.size() << "\n" ;
  lgl = lglinit();
  int len = std::strlen(argv[1]);
  std::cout << argv[1] << "\n   with length " << len << "\n";

  std::vector<A4> dirs;
  for(int i=0; i<len; ++i){
    switch(argv[1][i]){
    case 'N':
      dirs.emplace_back(A4{TRUELIT,FALSELIT,FALSELIT,FALSELIT});
      break;
    case 'E':
      dirs.emplace_back(A4{FALSELIT,TRUELIT,FALSELIT,FALSELIT});
      break;
    case 'S':
      dirs.emplace_back(A4{FALSELIT,FALSELIT,TRUELIT,FALSELIT});
      break;
    case 'W':
      dirs.emplace_back(A4{FALSELIT,FALSELIT,FALSELIT,TRUELIT});
      break;
    case '*': {
      dirs.emplace_back();
      std::generate_n(dirs[i].begin(),4,new_var);
      std::set<int> dirs_here { dirs[i].begin(), dirs[i].end() };
      at_most_one(dirs_here);
      clause(dirs_here);
      for(int l : dirs_here)
        lglfreeze(lgl,l);
      break;
      }
    default:
      usage(argv[0]);
    }
  }

  int maze_nr=0;
  for(;;) {
    std::cout << "Solving...\n";
    int res=lglsat(lgl);
    if(res==LGL_UNSATISFIABLE)
      unsat();
    assert(res==LGL_SATISFIABLE);
    std::string sol(len,' ');
    for(int i=0; i<len; ++i)
      for(int d=0; d<4; ++d)
        if (lit_is_true(dirs[i][d])){
          sol[i]=nesw[d];
          break;
    }
    std::cout << sol << "\n";

    Maze m=unsolved(str_to_moves(sol),mazes);
    if (m.is_dummy()){
      std::cout << "That solves all!\n";
      return 0;
    }
    std::cout << "Adding maze " << ++maze_nr << ": " <<
      m.walls << "/" << m.start <<
      " (" << m.size() << "/" << 12-m.simplicity() << ")\n";
    add_maze_conditions(m,dirs,len);
  }
}

```

First `configure.sh` and `make` the `lingeling` solver, then compile the program with something like `g++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl`, where `...` is the path where `lglib.h` resp. `liblgl.a` are, so both could for example be `../lingeling-<version>`. Or just put them in the same directory and do without the `-I` and `-L` options.

The program takes one mandatory command line argument, a string consisting of `N`, `E`, `S`, `W` (for fixed directions) or `*`. So you could search for a general solution of size 78 by giving a string of 78 `*`s (in quotes), or search for a solution starting with `NEWS` by using `NEWS` followed by as many `*`s as you want for additional steps. As a first test, take your favourite solution and replace some of the letters with `*`. This finds a solution fast for a surprisingly high value of "some".

The program will tell which maze it adds, described by wall structure and start position, and also give the number of reachable positions and walls. The mazes are sorted by these criteria, and the first unsolved one is added. Therefore most added mazes have `(9/4)`, but sometimes others appear as well.

I took the known solution of length 79, and for each group of adjacent 26 letters, tried to replace them with any 25 letters. I also tried to remove 13 letters from the beginning and from the end, and replace them by any 13 at the beginning and any 12 at the end, and vice versa. Unfortunately, it all came out unsatisfiable. So, can we take this as indicator that length 79 is optimal? No, I similarly tried to improve the length 80 solution to length 79, and that was also not successful.

Finally, I tried combining the beginning of one solution with the end of the other, and also with one solution transformed by one of the symmetries. Now I'm running out of interesting ideas, so I decided to show you what I have, even though it didn't lead to new solutions.
> 6 votes

---
Tags: code-challenge, grid, maze
---


title: Word Changer Reachability

text:
# Question
Title: Word Changer Reachability
Word changer is a game where you are trying to turn one word into another via single-character edits, with each step being its own word. For this challenge, edits may be replacements, insertions, or deletions. For example, WINNER → LOSER can be done with this route (there may be others):

```
WINNER
DINNER
DINER
DINE
LINE
LONE
LOSE
LOSER

```

Phrased another way, you must be able to reach one word from the other going only through other words at a Levenshtein distance of 1 each time.

# Coding

You will be given a word list and two words and you must output a valid route from one word to the other if a route exists or a distinct constant value or consistent behavior if no route exists.

* You may assume that the input words are both in the word list
* The word list can be taken in via any convenient flat format.
    + Lists, sets, tries, space-separated strings, and line-separated files are all valid (for instance), but a pre-computed graph of Levenshtein adjacency is not.
* The output route should include both input words, but which starts and ends doesn't matter.
* If no route is found, you can output a specific constant, a falsy value, empty list, throw an exception, exit with a nonzero code, or any other behavior that happens in finite time.
* The route does not need to be optimal and there is no requirement of which route should be taken
* Computational complexity does not matter, however your program must be provably guaranteed to terminate in a finite amount of time. (even if it would run beyond the heat death of the universe)
* You may assume all words are entirely composed of letters in the same case

# Example Test Cases

* CAT → DOG; \[CAT, DOG, COG, COT, FROG, GROG, BOG\]
    + CAT, COT, COG, DOG
* BATH → SHOWER; \[BATH, SHOWER, HATH, HAT, BAT, SAT, SAW, SOW, SHOW, HOW\]
    + No Route Found
* BREAK → FIX; \[BREAK, FIX, BEAK, BREAD, READ, BEAD, RED, BED, BAD, BID, FAD, FAX\]
    + BREAK, BREAD, BEAD, BAD, FAD, FAX, FIX
* BUILD → DESTROY; \[BUILD, DESTROY, BUILT, GUILT, GUILD, GILD, GILL, BILL, DILL, FILL, DESTRUCT, STRUCTURE, CONSTRUCT\]
    + No Route Found
* CARD → BOARD; \[CARD, BOARD, BARD\]
    + CARD, BARD, BOARD
* DEMON → ANGEL; \[DEMON, ANGEL\]
    + No Route Found
* LAST → PAST; \[LAST, PAST, BLAST, CAST, BLACK, GHOST, POST, BOAST\]
    + LAST, PAST
* INSERT → DELETE; This word list
    + INSERT, INVERT, INVENT, INBENT, UNBENT, UNBEND, UNBIND, UNKIND, UNKING, INKING, IRKING, DIRKING, DARKING, DARLING, ARLING, AILING, SIRING, SERING, SERINE, NERINE, NERITE, CERITE, CERATE, DERATE, DELATE, DELETE

# Answer
# 05AB1E, ~~23~~ ~~21~~ 20 bytes

Prints a list of valid routes.
Saved 2 bytes thanks to *Kevin Cruijssen*.

```
æ€œ€`ʒü.LP}ʒ¬²Qsθ³Q*

```

Try it online!
> 5 votes

# Answer
# JavaScript (V8),  ~~177~~  176 bytes

Takes input as `(target)(source, list)`. Prints all possible routes. Or prints nothing if there's no solution.

```
t=>F=(s,l,p=[],d)=>s==t?print(p):l.map((S,i)=>(g=(m,n)=>m*n?1+Math.min(g(m-1,n),g(m,--n),g(--m,n)-(S[m]==s[n])):m+n)(S.length,s.length)^d||F(S,L=[...l],[...p,L.splice(i,1)],1))

```

Try it online!

### Commented

```
t =>                            // t = target string
F = (                           // F is a recursive function taking:
  s,                            //   s = source string
  l,                            //   l[] = list of words
  p = [],                       //   p[] = path
  d                             //   d = expected Levenshtein distance between s and the
) =>                            //       next word (initially undefined, so coerced to 0)
  s == t ?                      // if s is equal to t:
    print(p)                    //   stop recursion and print the path
  :                             // else:
    l.map((S, i) =>             //   for each word S at index i in l[]:
      ( g =                     //     g = recursive function computing the Levenshtein
        (m, n) =>               //         distance between S and s
        m * n ?                 //       if both m and n are not equal to 0:
          1 + Math.min(         //         add 1 to the result + the minimum of:
            g(m - 1, n),        //           g(m - 1, n)
            g(m, --n),          //           g(m, n - 1)
            g(--m, n) -         //           g(m - 1, n - 1), minus 1 if ...
            (S[m] == s[n])      //           ... S[m - 1] is equal to s[n - 1]
          )                     //         end of Math.min()
        :                       //       else:
          m + n                 //         return either m or n
      )(S.length, s.length)     //     initial call to g with m = S.length, n = s.length
      ^ d ||                    //     unless the distance is not equal to d,
      F(                        //     do a recursive call to F with:
        S,                      //       the new source string S
        L = [...l],             //       a copy L[] of l[]
        [...p, L.splice(i, 1)], //       the updated path (removes S from L[])
        1                       //       an expected distance of 1
      )                         //     end of recursive call
    )                           //   end of map()

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), 59 bytes

```
Select[Rule@@@#~Tuples~2,EditDistance@@#<2&]~FindPath~##2&;

```

Try it online!
> 3 votes

# Answer
# Python 2, 155 bytes

```
f=lambda a,b,W,r=[]:a==b and r+[a]or reduce(lambda q,w:q or any({a,a[:i]+a[i+1:]}&{w,w[:i]+w[i+1:]}for i in range(len(a+w)))and f(w,b,W-{a},r+[a]),W-{a},0)

```

Try it online!

Takes two words and a set of words as input; returns a (non-optimal) route if one exists as a list of strings, otherwise returns False.

This fragment:

```
any({a,a[:i]+a[i+1:]}&{w,w[:i]+w[i+1:]}for i in range(len(a+w)))

```

is `True` if and only if `a==w` or `a` has Levenshtein distance of `1` from `w`.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 124 bytes

```
Join[#,Select[Flatten[Permutations/@Subsets@#3,1],s=#;t=#2;Union[EditDistance@@@Partition[Join[s,#,t],2,1]]=={1}&][[1]],#2]&

```

Try it online!
> 2 votes

# Answer
# Python 2, 163 bytes

If a route is found, it is output to stderr and the program exits with exit code 1.
If there is no route, there is no output and the program terminates with exit code 0.

```
s,e,d=input();r=[[s]]
for x in r:t=x[-1];t==e>exit(x);r+=[x+[w]for w in d-set(x)for a,b in(t,w),(w,t)for i in range(len(b)*2)if a==b[:i/2]+a[i/2:][:i%2]+b[i/2+1:]]

```

Try it online!
> 2 votes

# Answer
# Python 3, ~~217~~ ~~214~~ ~~212~~ 201 bytes

*-11 bytes thanx to a hint from xnor*

```
d=lambda a,b:min(d(a[1:],b[1:])+(a[0]!=b[0]),d(a[1:],b)+1,d(a,b[1:])+1)if b>""<a else len(a+b)
def g(a,b,l,p=[]):
	if a==b:yield[a]+p
	for c in(a!=b)*l:
		if(c in p)+d(a,c)==1:yield from g(c,b,l,[a]+p)

```

Try it online!
> 1 votes

# Answer
# Jelly, 38 bytes

```
⁵ḟ,€0ị$ṭ¹-Ƥ$€e€/ẸƊƇḢ€
Wṭ@ⱮÇßƊe@⁴oṆƲ?€Ẏ

```

Try it online!

A full program accepting three arguments. The first is the starting word and is supplied as `[["START"]]`. The second argument is the final word, supplied as `"END"`. The third argument is the word list, supplied as quoted, comma-separated words.

The program returns a list of lists, with each list representing a valid path from the start to the end. If there is no valid route, the response is an empty list.

In the TIO link, there is footer text to display the result nicely with each word separated by spaces and each list of words separated by newlines. If a printout underlying list representation is preferred, this could be done as `ÇŒṘ`.

Unlike 05ABIE, there’s no built-in for Levenshtein distance, so this program compares outfixes with a single character missing, somewhat similar to @ChasBrown’s solution, although with a Jelly twist.

### Explanation

Helper link: monadic link that takes a list of words and returns a list of possible extended lists, or an empty list if no further extension is possible

```
⁵ḟ                      | Filter the word list to remove words already used
  ,€0ị$                 | Pair each word with the last word in the current path
                  ƊƇ    | Filter these pairs such that
              e€/Ẹ      |   there exists any
       ṭ¹-Ƥ$€           |   match between the original words or any outfix with a single character removed
                    Ḣ€  | Take the first word of each of these pairs (i.e. the possible extensions of the route)

```

Main link

```
              €         | For each of the current paths
            Ʋ?          | If:
       e@⁴              |   The path contains the end word
          oṆ            |   Or the path is empty (i.e. could not be extended)
W                       | Return the path wrapped in a list (which will be stripped by the final Ẏ)
 ṭ@ⱮÇ                   | Otherwise, look for possible extensions using the helper link, and add onto the end of the path
     ßƊ                 | And then feed all of these paths back through this link
               Ẏ        | Strip back one layer of lists (needed because each recursion nests the path one list deeper)

```
> 0 votes

# Answer
# Swift 4.2/Xcode 10.2.1, 387 bytes

```
func d(l:String,m:String)->Bool{return (0..<l.count).contains{var c=l;c.remove(at:c.index(c.startIndex,offsetBy:$0));return c==m}};func f(r:[String])->[String]{if b==r.last!{return r};return w.lazy.map{!r.contains($0)&&(d(l:r.last!,m:$0)||d(l:$0,m:r.last!)||(r.last!.count==$0.count&&zip(r.last!,$0).filter{$0 != $1}.count==1)) ? f(r:r+[$0]):[]}.first{!$0.isEmpty} ?? []};return f(r:[a])

```

Try it online!
> 0 votes

---
Tags: code-golf, string, decision-problem
---


title: Convert Numbers To Emoji Math

text:
# Question
Title: Convert Numbers To Emoji Math
In Emoji Math, a user created module for the video game Keep Talking And Nobody Explodes, numbers are written as strings of emoticons, where each emoticon represents a base 10 digit. Below is the conversion table between digits and emoticons.

```
Digit | Emoticon
  0   |    :)
  1   |    =(
  2   |    (:
  3   |    )=
  4   |    :(
  5   |    ):
  6   |    =)
  7   |    (=
  8   |    :|
  9   |    |:

```

Given a number, output it in Emoji Math encoding. You may assume the absence of non-numeric characters.

This is , so the shortest answer in bytes wins.

# Answer
> 5 votes
# Japt, ~~29~~ 24 bytes

*-5 bytes thanks to @Shaggy*

```
s":)=((:)=:():=)(=:||:"ò

```

Takes input as a string

Try it online!

# Answer
> 5 votes
# 05AB1E, 26 bytes

```
"|:(=):)=:)"2ôºJ2ô`Šr)sSèJ

```

Try it online!

# Answer
> 5 votes
# C (gcc), ~~62~~ 58 bytes

-4 bytes thanks to ceilingcat

```
f(n){n&&write(1,":)=((:)=:():=)(=:||:"+n%10*2,2,f(n/10));}

```

Try it online!

# Answer
> 4 votes
# Python 2, ~~65~~ 62 bytes

```
lambda n:''.join(':=():)=(:|)(:=(:)=|:'[int(c)::10]for c in n)

```

Try it online!

# Answer
> 4 votes
# TI-BASIC, 79 bytes

```
Ans→Str1:" :For(I,1,length(Str1:Ans+sub(":)=((:)=:():=)(=:||:",1+2expr(sub(Str1,I,1)),2:End:sub(Ans,2,length(Ans)-1

```

Input is a string of digits in `Ans`.
Output is the Emoji Math-encoded number.

**Examples:**

```
"134
134
prgmCDGF1C
:)(:)=
"2213894
2213894
prgmCDGF1C
(:(:=()=:||::(

```

**Explanation:**

```
Ans→Str1                                                 ;store the input in Ans
"                                                        ;leave " " in Ans
For(I,1,length(Str1                                      ;loop over each character in the
                                                         ; input string
Ans+sub(":)=((:)=:():=)(=:||:",1+2expr(sub(Str1,I,1)),2  ;convert the current character
                                                         ; to a number and use it as the
                                                         ; index into the encoding string
                                                         ; then append the encoded digit
End
sub(Ans,2,length(Ans)-1                                  ;remove the prepended space and
                                                         ; store the result in Ans
                                                         ;implicit print of Ans

```

---

Alternatively, here's a **94 byte** solution that takes a number as input instead of a string:

```
int(10fPart(Ans₁₀^(seq(⁻X-1,X,0,log(Ans→L₁:" :For(I,dim(L₁),1,-1:Ans+sub(":)=((:)=:():=)(=:||:",1+2L₁(I),2:End:sub(Ans,2,length(Ans)-1

```

**Examples:**

```
134
             134
prgmCDGF1C
:)(:)=
2213894
         2213894
prgmCDGF1C
(:(:=()=:||::(

```

**Explanation:**

```
int(10fPart(Ans₁₀^(seq(⁻X-1,X,0,log(Ans→L₁     ;generate a list of the input's digits
                                             ; reversed and store it in L₁
"                                            ;leave " " in Ans
For(I,dim(L₁),1,-1                            ;loop over L₁ backwards
Ans+sub(":)=((:)=:():=)(=:||:",1+2L₁(I),2     ;use the value of the I-th element in L₁ as
                                              ; the index into the encoding string then
                                              ; append the encoded digit
End
sub(Ans,2,length(Ans)-1                       ;remove the prepended space and store the
                                              ; result in Ans
                                              ;implicit print of Ans

```

---

**Notes:**

# Answer
> 3 votes
# Perl 5 `-p`, 42 bytes

```
s/./substr":)=((:)=:():=)(=:||:",$&*2,2/ge

```

Try it online!

# Answer
> 3 votes
# \[R\],  ~~59~~  48 bytes

different approach:

```
 substr(":)=((:)=:():=)(=:||:",n<-2*scan()+1,n+1)

```

thanks to @aaron for directing me on again :)

original:

```
 el(strsplit(":)x=(x(:x)=x:(x):x=)x(=x:|x|:","x",T))[scan()]

```

beats

```
 c(":)","=(","(:",")=",":(","):","=)","(=",":|","|:")[scan()]

```

by 1 byte

# Answer
> 3 votes
# JS ES6, 77 66 bytes

Down to 66 thanks to suggestions from @Charlie Harding and @asgallant

Had to finally make an account on codegolf since this was such a fun little challenge!

The most minimal form of the original answer, when expecting string-only input:

```
n=>[...n].map(c=>":)=((:)=:():=)(=:||:".match(/../g)[c]).join("")

```

Secondly, my original answer which uses a longer regex and first coerces the input into a string, This works with both number type input and a string of digits input.

> I first coerce the input into a string, which is then destructured into an array using es6 spread. Then I map it through a matcher cb that grabs the correct emoticon from an array made with the regex `/.{1,2}/g`. Finally the resulting array of emoticons is joined back to a string.

```
n=>[...(""+n)].map(c=>":)=((:)=:():=)(=:||:".match(/.{1,2}/g)[c]).join("")

```

JS array stuff is fun. I'm sure there's still some room for optimization, this re-matches the regex on every loop of the `map`.

Crappily tested with the following:

```
let emoticonize = n=>[...(""+n)].map(c=>":)=((:)=:():=)(=:||:".match(/../g)[c]).join("")

let test = arr =>
console.log(arr.map(x => ({ask:x, ans: emoticonize(x)})))

test([1,40,3697, 2330])
test(["1","40","3697", "2330"])
```

# Answer
> 3 votes
# Java 8, 80 bytes

```
n->n.forEach(i->System.out.print(":)=((:)=:():=)(=:||:".split("(?<=\\G..)")[i]))

```

Try it online.

**Explanation:**

```
n->                           // Method with IntStream parameter and no return-type
  n.forEach(i->               //  For each digit `i` in the input:
    System.out.print(         //   Print without newline:
      ":)=((:)=:():=)(=:||:"  //    Push this String
        .split("(?<=\\G..)")  //    Split into parts of size 2
          [i]))               //    And print the `i`'th part

```

# Answer
> 3 votes
# Haskell, ~~64~~ 56Laikoni bytes

```
((words":) =( (: )= :( ): =) (= :| |: "!!).read.pure=<<)

```

Try it online

### Ungolfed

Apply the function `words` to our space-separated string of symbols `":) =( (: )= :( ): =) (= :| |: "` to get a list, and get the *n*th element `(!!)` for every *n* in our input string, combining the results. *n.b.* `(=<<)` is equivalent to `concatMap` in this case, mapping a string to a list of strings and concatenating the results. `read . pure` converts a character to an int, by lifting a character to a string, then `read`ing to an int.

```
f x = ((words ":) =( (: )= :( ): =) (= :| |: " !!) . read . pure) =<< x

```

# Answer
> 2 votes
# Jelly, 21 bytes

```
“=:)|(”“ØḟƝoṣẈ’ṃs2ị@D

```

Try it online!

# Answer
> 2 votes
# Icon, ~~78~~ 75 bytes

```
procedure f(n);s:="";s||:=":)=((:)=:():=)(=:||:"[!n*2+1+:2]&/n;return s;end

```

Try it online!

# Answer
> 2 votes
## C# (Visual C# Interactive Compiler), ~~87~~, ~~86~~, ~~82~~, 67 bytes

Props to @Artholl and @someone for helping to optimize

```
n=>$"{n}".SelectMany(x=>":)=((:)=:():=)(=:||:".Substring(x*2-96,2))

```

Try it online!

# Answer
> 2 votes
# PowerShell, ~~64~~ ~~60~~ 59 bytes

-1 byte thanks to mazzy

```
-join($args|% t*y|%{':)=((:)=:():=)(=:||:'|% S*g(2*"$_")2})

```

Try it online!

Takes a string, splits it in `toCharArray`, and then indexes into the emoji key by casting the character to its numerical value, doubles it because each emoji is two wide, and then takes the `substring` from that spot plus one higher. Finally it joins this all up into one string and pushes it to output.

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

```
n=>{for(s=":)=((:)=:():=)(=:||:",i=0;i<20;)n=n.split(i/2).join(s[i++]+s[i++]);return n}

```

# Answer
> 1 votes
# Jelly, 24 bytes

```
“LƇ§×Yþ’ḃ5$s2ị“:)=(|”ị@D

```

Try it online!

# Answer
> 1 votes
# Attache, 34 bytes

```
Chop[":)=((:)=:():=)(=:||:",2]&Get

```

Try it online!

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


title: Make me a minimum magic sum

text:
# Question
Title: Make me a minimum magic sum
Keeping this challenge short.

You are given 4 numbers: p1, p2, p3 and p4.

The magic sum of the numbers are defined as follows:

```
magic_sum = |p1 - p2| + |p2 - p3| + |p3 - p4| + |p4 - p1|

```

You are only allowed to change one of the above integer values (p1, p2, p3 or p4). You need to change the value such that the magic sum of the values attains its minimum value.

For example:

p1, p2, p3, p4 = 17, -6, 15, 33. The value of the magic sum is 78 in this case.

You can change the -6 here to 16, and the value of the magic sum will become 36, which is the minimum attainable value.

Do keep in mind that numbers can be positive or negative integers.

This is code-golf, so least bytes in code wins. Brownie points for using a Practical Language over a Recreational language. May the 4th be with you.

To reiterate:

### Sample 1

**Input 1**

```
17 -6 15 33

```

**Output 1**

```
36

```

**Explanation 1**

> The -6 can be replaced with 16 and that gives us the minimum attainable magic sum possible.

### Sample 2

**Input 2**

```
10 10 10 10

```

**Output 2**

```
0 or 2

```

either is acceptable

**Explanation 2**

> The minimum attainable magic sum is 0 since the minimum sum of 4 positive integers is 0. If a number has to be changed, then one of the 10's can be changed to a 9 and thus yielding the output 2.

## Sample 3

**Input 3**

```
1 2 3 4

```

**Output 3**

```
4

```

**Explanation 3**

> The input by itself yields 6 as its magic sum. Changing the 4 to 1 and the minimum magic sum is attained, which is 4.

# Answer
# Jelly, 6 bytes

```
ṢŒœIṂḤ

```

Try it online!

A port of my Python answer.

```
     (input)        [17, -6, 15, 33]
Ṣ    sort           [-6, 15, 17, 33]
Œœ   odd-even elts  [[-6, 17], [15, 33]]
I    increments     [23, 18]
M    minimum        18
Ḥ    double         36

```
> 14 votes

# Answer
# Python 2, 44 bytes

```
a,b,c,d=sorted(input())
print min(c-a,d-b)*2

```

Try it online!

Sorts the input as `a,b,c,d,` in ascending order, takes the smaller of `c-a` and `d-b`, and doubles it. Why does this work?

First, note that when we change an element to maximize to total cyclic sum of distances, it's optimal (or tied for optimal) to change it to equal a neighbor, such as `17, -6, 15, 33 -> 17, 17, 15, 33`. That's because its new total distance to its left and right cyclic neighbors is at least the distance between those neighbors, so making these be equal is the best we can do.

Now, deleting one of two adjacent copies of a number gives the same cyclic sum of distances. In the example, this is `17, 15, 33`, giving distances `2 + 18 + 16`. So instead of replacing one of the four numbers, it's equivalent to just delete it leaving three numbers, and using the sum of their cyclic distances.

Notice that with 3 numbers, the largest distance is the sum of the two smaller ones. This is because if we sort the numbers to have `a ≤ b ≤ c`, then `|a - c| = |a - b| + |b - c|`. In other words, we travel between the largest and smallest number twice, using the medium number as a pit stop one of the times. So, the sum of the three distances is just twice the distance between the minimum and maximum, so `(c-a)*2`.

So, the question is which number we delete to get the smallest distance between the minimum and maximum of the three numbers that remains. Clearly we delete either the smallest or the largest of the numbers. Calling them `a, b, c, d` in sorted order, deleting `a` leaves `d - b`, and deleting `d` leaves `c - a`, and the final result is double whichever is smaller.
> 20 votes

# Answer
# , ~~66~~ 33 bytes

```
function(x)2*min(diff(sort(x),2))

```

Try it online!

Much shorter with xnor's algorithm (go read their explanation and upvote their post!).

Old version:

# , 66 bytes

```
function(x,m=matrix(x,3,4))min(colSums(abs(diff(rbind(m,m[1,])))))

```

Try it online!

Takes input as a vector of 4 integers.

This works because the minimum can be attained by setting one of the numbers as equal to one of its neighbours (it is not the only way of attaining the minimum). To see why this is true, find a configuration which achieves the minimum; say we have changed \\$p\_2\\$. Any value of \\$p\_2\\$ such that \\$p\_1\leq p\_2\leq p\_3\\$ will give the same sum (\\$|p\_1-p\_2|+|p\_2-p\_3|\\$ remains constant), so we can choose \\$p\_2=p\_1\\$.

There are 4 ways of choosing which number we change; for each of these, we only have to compute the sum of 3 absolute differences.

The code sets the values in a \\$3\times4\\$ matrix, where each column represents a subset of size 3 of the 4 numbers. Copy the first row to a 4th row with `rbind` and compute the absolute differences, then take the minimum of the column sums.
> 9 votes

# Answer
# Jelly, ~~11~~ 10 bytes

```
I;SASƲ$-ƤṂ

```

Try it online!

A monadic link that takes a list if integers as input. Should work for arbitrary list size. Works on the basis that the minimum sum can be obtained by testing removing each number from the list, calculating the magic sum and taking the minimum.
> 4 votes

# Answer
# Japt `-Q`, 11 bytes

```
ñÍó ®r- ÑÃn

```

Uses @xnor's algorithm, which saved me 4 bytes.

Saved 5 bytes thanks to @Shaggy

Try it
> 3 votes

# Answer
# Jelly, 8 bytes

```
ṁ-Ƥ⁸IA§Ṃ

```

A monadic Link accepting a list of integers\* which yields an integer

* can be any number so long as there are more than 1; using same style magic formula summing the neighbours differences wrapping around.

**Try it online!**

### How?

```
ṁ-Ƥ⁸IA§Ṃ - Link: list of integers, X       e.g. [17,-6,15,33]
 -Ƥ      - for overlapping "outfixes" of length length(X)-1:
         -                                      [[-6,15,33],[17,15,33],[17,-6,33],[17,-6,15]]
ṁ  ⁸     -   mould like X                       [[-6,15,33,-6],[17,15,33,17],[17,-6,33,17],[17,-6,15,17]]
    I    - incremental differences              [[21,18,-39],[-2,18,-16],[-23,39,-16],[-23,21,2]]
     A   - absolute (vectorises)                [[21,18,39],[2,18,16],[23,39,16],[23,21,2]]
      §  - sums                                 [78,36,78,46]
       Ṃ - minimum                              36

```
> 3 votes

# Answer
# , ~~24~~ ~~20~~ ~~18~~ 17 bytes

alternative version using xnor algorithm:

```
2*[:<./2 2-/@$\:~

```

## how

Two times `2 *` the min of `[:<./` the 2nd row subtracted from the first row `[:-/` of the 2x2 matrix formed by shaping `2 2$` the input sorted down `\:~`

Try it online!

## original answer: , 24 bytes

```
[:<./1(1#.2|@-/\],{.)\.]

```

Try it online!

Using Nick Kennedy's idea.

* `1(...)\.]` apply the verb in parens to all outfixes of length 1 (an outfix of length n is a list with n contiguous elements removed, so this produces every possible list with 1 elm removed)
* `(1 #. 2 |@-/\ ] , {.)` this calculates the magic sum by appending the first elm to the input `] , {.` and applying the abs difference `|@-/` to infixes of length 2 `2 ...\`, and summing the result `1 #.`.
* `[:<./` returns the min
> 3 votes

# Answer
# 05AB1E, ~~11~~ 7 bytes

Port of *@xnor*'s Jelly answer.
-4 bytes thanks to *@Emigna* and *@Grimy*.

```
{2ô`αß·

```

Try it online.

**7 bytes alternative** which only works in the legacy version of 05AB1E (would require a  before the `¥` in the new version):

```
{2ôø¥W·

```

Try it online.

**Explanation:**

```
{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   `     # Push both separated to the stack
    α    # And take their absolute differences
         #  → [23,18]
     ß   # Pop and push the minimum
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36

{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   ø     # Zip/transpose, swapping rows/columns
         #  → [[-6,17],[15,33]]
    ¥    # Get the deltas/forward differences of the inner lists
         #  → [[23],[18]]
     W   # Get the flattened minimum (without popping)
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36

```
> 2 votes

# Answer
# C++ (gcc)

## full program: 138 bytes

```
#include<iostream>
#include<regex>
using namespace std;int main(){int a[4];for(int&b:a)cin>>b;sort(a,a+4);cout<<min(a[2]-*a,a[3]-a[1])*2;}

```

Try it online!

## core function: 84 bytes

```
#include<regex>
int m(int*a){std::sort(a,a+4);return std::min(a[2]-*a,a[3]-a[1])*2;}

```

Try it online!

Also using the algorithm *xnor* explained in his Python 2 post.
> 1 votes

# Answer
# JavaScript (ES6), 51 bytes

Using xnor's much more clever method:

```
a=>([a,b,c,d]=a.sort((a,b)=>a-b),b+c<a+d?c-a:d-b)*2

```

Try it online!

---

# Original answer, 96 bytes

Takes input as an array of 4 integers. ~~Probably~~ Definitely not the shortest approach.

```
a=>a.map(m=x=>a.map((y,i)=>a[m=a.map(v=>s+=Math.abs(p-(p=v)),a[i]=x,p=a[3],s=0)|m<s?m:s,i]=y))|m

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), 29 bytes

A port of @xnor's algorithm

```
2{#3-#}~Min~{#4-#2}&@@Sort@#&

```

Try it online!
> 0 votes

# Answer
# Charcoal, 20 bytes

```
Ｉ⌊ＥＥθΦθ⁻κμΣＥι↔⁻λ§ι⊕μ

```

Try it online! Link is to verbose version of code. Turns out I'm using @NickKennedy's idea. Explanation:

```
   Ｅθ                   Map over input array
     Φθ                 Filter over input array where
       ⁻κμ              Outer and inner indices differ
  Ｅ                     Map over resulting list of lists
           Ｅι           Map over remaining values in list
                §ι⊕μ    Get the next value in the list
             ↔⁻λ        Compute the absolute difference with the current value
          Σ             Take the sum of absolute differences
 ⌊                      Take the minimum sum
Ｉ                       Cast to string and implicitly print

```
> 0 votes

# Answer
# Java 8, 235 bytes

A port of @xnor's Python answer and algorithm

```
import java.util.*;interface M{static void main(String[]A){Scanner I=new Scanner(System.in);int a[]={0,0,0,0};for(int i=0;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}

```

Try it online!

### Java 10, unproven, 222 bytes

With Java 10, I should be able to replace left side of Scanner declaration with `var`, although I could not compile it online and thus I can only add it as a trivia. Sorry.

```
interface M{static void main(String[]A){var I=new java.util.Scanner(System.in);int a[]={0,0,0,0};for(int i=3;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}

```
> 0 votes

---
Tags: code-golf, optimization
---


# Question
Title: Rock, Paper, Scissors, Lizard, Spock Tournament
Giving a challenge involving a Star Trek reference just after May the 4th may be frowned upon, but here goes.

You, Luke, Anakin, Palpatine, Yoda and Han Solo are involved in an insane tournament of Rock, Paper, Scissor, Lizard, Spock.

The catch here is that you are only allowed to use a fixed order of moves. If your order is "R", Then you have to use Rock, until you lose or win against everyone. If your order is RRV, then you have to use 2 Rocks followed by a Spock and keep repeating until you have won or lost.

Luke, Anakin, Palpatine, Yoda and Han Solo have submitted their respective orderings and you being an expert hacker got your hands on each of their orderings!

With this knowledge, you are to design your ordering for the tournament. Since everyone wants to win, you want to create an ordering such that you win the tournament by beating everyone. But this may not be possible under all circumstances.

Incase there is a possible winning order, print that out. If there is no possible way for you to win, print out -1 (or 0 or False or "impossible")

**Input**: a list of 5 orders

**Output**: a single order or -1

**Sample Input 1**

```
R
P
S
L
V

```

**Sample Output 1**

```
-1

```

**Explanation 1**

> No matter what you play in your first move, there will be at least one person who beats you, hence it is not possible for you to win.

**Sample Input 2**

```
RPS
RPP
R
SRR
L

```

**Sample Output 2**

```
RPSP

```

**Explanation 2**

> Once you play Rock in your first move, you end up beating "L" and "SRR" and tie against the rest. This is because Lizard and Scissors lose to Rock. When you play Paper next, you will beat "R" and tie against the remaining 2. This is because Rock loses to Paper. When you play Scissors next, you will win against "RPP" as Scissor beats Paper.
>
> Finally, you will beat "RPS" with your Paper as Paper beats Rock.

Here are a list of notations (you may use any 5 literals, but please specify in your answer):

```
R : Rock
P : Paper
S : Scissor
L : Lizard
V : Spock

```

Here is a list of all possible outcomes:

```
winner('S', 'P') -> 'S'
winner('S', 'R') -> 'R'
winner('S', 'V') -> 'V'
winner('S', 'L') -> 'S'
winner('S', 'S') -> Tie
winner('P', 'R') -> 'P'
winner('P', 'V') -> 'P'
winner('P', 'L') -> 'L'
winner('P', 'S') -> 'S'
winner('P', 'P') -> Tie
winner('R', 'V') -> 'V'
winner('R', 'L') -> 'R'
winner('R', 'S') -> 'R'
winner('R', 'P') -> 'P'
winner('R', 'R') -> Tie
winner('L', 'R') -> 'R'
winner('L', 'V') -> 'L'
winner('L', 'S') -> 'S'
winner('L', 'P') -> 'L'
winner('L', 'L') -> Tie
winner('V', 'R') -> 'V'
winner('V', 'L') -> 'L'
winner('V', 'S') -> 'V'
winner('V', 'P') -> 'P'
winner('V', 'V') -> Tie

```

This is , so fewest bytes win.

P.S: Let me know if you need more test cases.

# Answer
> 2 votes
# Jelly, 29 bytes

```
_%5ḟ0ḢḂ¬
ṁ€ZLḤƊçþ`Ạ€Tị;‘%5Ɗ$€

```

A monadic Link that accepts a list of lists of integers (each of which is an opponent's strategy) which yields a list of lists of integers - each of which is a winning strategy (so an empty list if none are possible).
<sub>(Just add  to only yield a single strategy list or `0` if impossible.)</sub>

**Try it online!** (the footer formats to always show the lists)

```
Rock  Paper  Scissors  Spock  Lizard
0     1      2         3      4

```

Or try a letter mapped version (where strategies are taken and shown on their own lines using `RPSVL` notation).

### How?

The numbers are chosen such that any which are an odd number greater than another modulo five win (i.e. they are numbered going around the edge of an inscribed pentagon of the throws).

The code plays each strategy off against every strategy (including themselves) for twice as many throws as the longest strategy so as to ensure finding any losers keeping those which are not defeated. The resulting list of strategies will contain a single strategy if there is an outright winner; no strategies if there was no winner; or multiple strategies if there are drawing players. After this a winning set of moves is appended to each of these strategies.

```
_%5ḟ0ḢḂ¬ - Link 1, does B survive?: list A, list B (A & B of equal lengths)
                              e.g. RPSR vs RPVL ->  [0,1,2,0], [0,1,3,4]
_        - subtract (vectorises)                    [0,0,-1,-4]
 %5      - modulo five (vectorises)                 [0,0,4,1]   ...if all zeros:
   ḟ0    - filter discard zeros (ties)              [4,1]                       []
     Ḣ   - head (zero if an empty list)             4                           0
      Ḃ  - modulo two                               0                           0
       ¬ - logical NOT                              1                           1

ṁ€ZLḤƊçþ`Ạ€Tị;‘%5Ɗ$€ - Main Link: list of lists of integers
ṁ€                   - mould each list like:
     Ɗ               -   last three links as a monad
  Z                  -     transpose
   L                 -     length
    Ḥ                -     double  (i.e. 2 * throws in longest strategy)
        `            - use left as both arguments of:
       þ             -   table using:
      ç              -     last Link (1) as a dyad
         Ạ€          - all for each (1 if survives against all others, else 0)
           T         - truthy indices
            ị        - index into the input strategies
                  $€ - last two links as a monad for each:
             ;       -   concatenate with:
                 Ɗ   -     last three links as a monad:
              ‘      -       increment (vectorises)
               %5    -       modulo five (vectorises)

```

# Answer
> 7 votes
# JavaScript (ES6),  ~~122 115~~  112 bytes

Takes input as an array of strings of digits, with:

* \\$0\\$ = Scissors (S)
* \\$1\\$ = Paper (P)
* \\$2\\$ = Rock (R)
* \\$3\\$ = Lizard (L)
* \\$4\\$ = Spock (V)

Returns either a string in the same format or \\$false\\$ if there's no solution.

```
f=(a,m='',x=0,o,b=a.filter(a=>(y=a[m.length%a.length])-x?o|=y-x&1^x<y:1))=>b+b?x<4&&f(a,m,x+1)||!o&&f(b,m+x):m+x

```

Try it online!

### How?

This is a breadth-first search: we first try all moves at a given step to see if we can win the game. If we can't win right now, we try to add another move to each non-losing move.

The move identifiers were chosen in such a way that a move \\$A\\$ wins against a move \\$B\\$ if and only if \\$(B-A)\bmod 5\\$ is odd.

With \\$A\\$ on the left and \\$B\\$ on the top:

$$ \begin{array}{cc|ccccc} & & \text{(S)} & \text{(P)} & \text{(R)} & \text{(L)} & \text{(V)}\\ & & 0 & 1 & 2 & 3 & 4\\ \hline \text{(S) }&0 & - & \color{green}1 & \color{red}2 & \color{green}3 & \color{red}4\\ \text{(P) }&1 & \color{red}4 & - & \color{green}1 & \color{red}2 & \color{green}3\\ \text{(R) }&2 & \color{green}3 & \color{red}4 & - & \color{green}1 & \color{red}2\\ \text{(L) }&3 & \color{red}2 & \color{green}3 & \color{red}4 & - & \color{green}1\\ \text{(V) }&4 & \color{green}1 & \color{red}2 & \color{green}3 & \color{red}4 & - \end{array} $$

From there, we can deduce another way of testing if \\$A\\$ wins against \\$B\\$ for \\$A\neq B\\$:

```
((A - B) and 1) xor (B < A)

```

where `and` and `xor` are bitwise operators.

### Commented

```
f = (                        // f is a recursive function taking:
  a,                         //   a[] = input
  m = '',                    //   m   = string representing the list of moves
  x = 0,                     //   x   = next move to try (0 to 4)
  o,                         //   o   = flag set if we lose, initially undefined
  b =                        //   b[] = array of remaining opponents after the move x
    a.filter(s =>            //     for each entry s in a[]:
    ( y =                    //       define y as ...
      s[m.length % s.length] //         ... the next move of the current opponent
    ) - x                    //       subtract x from y
    ?                        //       if the difference is not equal to 0:
      o |=                   //         update o using the formula described above:
        y - x & 1 ^ x < y    //           set it to 1 if we lose; opponents are removed
                             //           while o = 0, and kept as soon as o = 1
    :                        //       else (this is a draw):
      1                      //         keep this opponent, but leave o unchanged
  )                          //     end of filter()
) =>                         //
  b + b ?                    // if b[] is not empty:
    x < 4 &&                 //   if x is less than 4:
      f(a, m, x + 1)         //     do a recursive call with x + 1 (going breadth-first)
    ||                       //   if this fails:
      !o &&                  //     if o is not set:
        f(b, m + x)          //       keep this move and do a recursive call with b[]
  :                          // else (success):
    m + x                    //   return m + x

```

# Answer
> 3 votes
# , ~~213~~ 190 bytes

-23 bytes thanks to Giuseppe.

```
function(L){m=matrix(rep(0:2,1:3),5,5)
m[1,4]=m[2,5]=1
v=combn(rep(1:5,n),n<-sum(lengths(L)))
v[,which(apply(v,2,function(z)all(sapply(L,function(x,y,r=m[cbind(x,y)])r[r>0][1]<2,z)))>0)[1]]}

```

Try it online!

If a solution exists, it outputs one. If there is no solution, it outputs a row of `NA`. If this output format is not acceptable, I can change it at a cost of a few bytes.

Moves are coded as 1=R, 2=S, 3=P, 4=L, 5=V, so that the matrix of outcomes is

```
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    2    2    1    1
[2,]    1    0    2    2    1
[3,]    1    1    0    2    2
[4,]    2    1    1    0    2
[5,]    2    2    1    1    0

```

(0=no winner; 1=player 1 wins; 2=player 2 wins)

An upper bound on the length of the solution if it exists is `n=sum(lengths(L))` where `L` is the list of opponents' moves. The code creates all possible strategies of length `n` (stored in matrix `v`), tries all of them, and displays all winning strategies.

Note that this value of `n` makes the code very slow on TIO, so I have hardcoded in the TIO `n=4` which is enough for the test cases.

For the first test case, the output is

```
     1 4 2 4

```

corresponding to the solution RLSL.

For the second test case, the output is

```
 NA NA NA NA

```

meaning that there is no solution.

Explanation of a previous version (will update when I can):

```
function(L){
  m = matrix(rep(0:2,1:3),5,5);
  m[1,4]=m[2,5]=1                      # create matrix of outcomes
  v=as.matrix(expand.grid(replicate(   # all possible strategies of length n
    n<-sum(lengths(L))                 # where n is the upper bound on solution length
    ,1:5,F)))
  v[which(
    apply(v,1,                         # for each strategy
          function(z)                  # check whether it wins
            all(                       # against all opponents
              sapply(L,function(x,y){  # function to simulate one game
                r=m[cbind(x,y)];       # vector of pair-wise outcomes
                r[r>0][1]<2            # keep the first non-draw outcome, and verify that it is a win
              }
              ,z)))
    >0),]                              # keep only winning strategies
}

```

The `which` is necessary to get rid of NAs which occur when the two players draw forever.

I am not convinced this is the most efficient strategy. Even if it is, I am sure that the code for `m` could be golfed quite a bit.

# Answer
> 0 votes
# Emacs Lisp, 730 bytes

```
(require 'cl-extra)
(require 'seq)
(defun N (g) (length (nth 1 g)))
(defun M (g) (mapcar (lambda (o) (nth (% (N g) (length o)) o)) (car g)))
(defun B (x y) (or (eq (% (1+ x) 5) y) (eq (% (+ y 2) 5) x)))
(defun S (g) (seq-filter (lambda (m) (not (seq-some (lambda (v) (B v m)) (M g)))) '(0 1 2 3 4)))
(defun F (g) (cond ((null (car g)) (reverse (nth 1 g))) ((null (S g)) nil) ((>= (nth 3 g) (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y)) (mapcar 'length (car g)) 1)) nil) (t (cl-some (lambda (m) (F   (let ((r (seq-filter 'identity (mapcar* (lambda (v o) (and (not (B m v)) o)) (M g) (car g))))) (list r (cons m (nth 1 g)) (1+ (N g)) (if (eq (car g) r) (1+ (nth 3 g)) 0))))) (S g)))))
(defun Z (s) (F (list s () 0 0)))

```

I didn't find an online interpreter of Emacs Lisp :( If you have Emacs installed, you can copy code into a `.el` file, copy some testing lines below

```
;; 0 = rock, 1 = lizard; 2 = spock;
;; 3 = scissors; 4 = paper
(print (Z '((0) (1) (2) (3) (4))))
; output: nil
(print (Z '((0) (4) (3) (1))))
; output: nil
(print (Z '((0 4 3) (0 4 4) (0) (3 0 0) (1))))
; output: (0 4 3 0 1)
(print (Z '((4) (4) (3) (4) (4))))
; output: (3 0)
(print (Z '((4 3 2 1 0) (2 1 0 4 3))))
; output: (1)
(print (Z '((2) (2) (3) (0) (2) (3) (0) (0))))
; output: (2 1)
(print (Z '((2) (2 0) (3) (0) (2 1) (3) (0) (0))))
; output: nil

```

and run it `$ emacs --script filename.el`.

## How it works

My program does depth first search with sometimes figuring out that it's impossible to win and terminating the branch it's on.

You can see full explanation in the unshortened version of the code:

```
(require 'seq)
(require 'cl-extra)

;; This program does depth first search with sometimes figuring out
;; that it's impossible to win and terminating the branch it's on.
;;

;; A move is a number from 0 to 4.
;; https://d3qdvvkm3r2z1i.cloudfront.net/media/catalog/product/cache/1/image/1800x/6b9ffbf72458f4fd2d3cb995d92e8889/r/o/rockpaperscissorslizardspock_newthumb.png
;; this is a nice visualization of what beats what.
;; Rock = 0, lizard = 1, spock = 2, scissors = 3, paper = 4.

(defun beats (x y) "Calculates whether move x beats move y"
  (or (eq (% (1+ x) 5) y)
      (eq (% (+ y 2) 5) x)))

;; A gamestate is a list with the following elements:
(defun get-orders (gamestate)
  "A list of orders of players who haven't lost yet. Each order is a list of moves.
For example, ((2) (2 0) (3) (0) (2 1) (3) (0) (0)) is a valid orders list.
This function gets orders from the gamestate."
  (car gamestate))

;; At index 1 of the gamestate lies a list of all moves we have made so far in reverse order
;; (because lists are singly linked, we can't push back quickly)
(defun get-num-moves-done (gamestate)
  "Returns the number of moves the player has done so far"
  (length (nth 1 gamestate)))

(defun get-rounds-since-last-elim (gamestate)
  "The last element of a gamestate is the number of rounds passed since an opponent
was eliminated. We use this to determine if it's possible to win from current
gamestate (more about it later)."
  (nth 2 gamestate))

;; next go some utility functions
;; you can skip their descriptions, they are not very interesting
;; I suggest you skip until the next ;; comment

(defun get-next-move (order num-rounds-done)
  "Arguments: an order (e.g. (1 0 1)); how many rounds have passed total.
Returns the move this opponent will make next"
  (nth (% num-rounds-done (length order)) order))

(defun moves-of-opponents-this-round (gamestate)
  "Returns a list of moves the opponents will make next"
  (mapcar (lambda (order) (get-next-move order (get-num-moves-done gamestate)))
          (get-orders gamestate)))

(defun is-non-losing (move opponents-moves)
  "Calculates if we lose right away by playing move against opponents-moves"
  (not (seq-some (lambda (opponent-move) (beats opponent-move move))
                 opponents-moves)))

(defun non-losing-moves (gamestate)
  "Returns a list of moves which we can play without losing right away."
  (seq-filter
   (lambda (move) (is-non-losing move (moves-of-opponents-this-round gamestate)))
   '(0 1 2 3 4)))

(defun advance-gamestate (gamestate move)
  "If this move in this gamestate is non-losing, returns the next game state"
  (let ((new-orders (seq-filter
                    'identity (mapcar* (lambda (opp-move order)
                                         (and (not (beats move opp-move)) order))
                                       (moves-of-opponents-this-round gamestate)
                                       (get-orders gamestate)))))
  (list new-orders
        (cons move (nth 1 gamestate))
        (if (eq (get-orders gamestate) new-orders) (1+ (get-rounds-since-last-elim gamestate)) 0))))

;; How do we prevent our depth first search from continuing without halting?
;; Suppose 3 players (except us) are still in the game and they have orders of lengths a, b, c
;; In this situation, if least_common_multiple(a, b, c) rounds pass without an elimination
;; we will be in the same situation (because they will be playing the same moves they played
;; lcm(a, b, c) rounds ago)
;; Therefore, if it's possible to win from this gamestate,
;; then it's possible to win from that earlier game state,
;; hence we can stop exploring this branch

(defun get-cycle-len (gamestate)
  "Returns a number of rounds which is enough for the situation to become the same
if the game goes this long without an elimination."
  (seq-reduce (lambda (x y) (calc-eval "lcm($,$$)" 'raw x y))
              (mapcar 'length (get-orders gamestate)) 1))

(defun unwinnable-cycle (gamestate)
  "Using the aforementioned information, returns t if we are in such a
suboptimal course of play."
  (>= (get-rounds-since-last-elim gamestate) (get-cycle-len gamestate)))

(defun find-good-moves (gamestate)
  "Given gamestate, if it's possible to win
returns a list of moves, containing all moves already done + additional moves which lead to win.
Otherwise returns nil"
  (cond ((null (get-orders gamestate)) ; if no opponents left, we won, return the list of moves
         (reverse (nth 1 gamestate)))
        ((null (non-losing-moves gamestate)) ; if no non-losing moves available, this gamestate
         nil) ; doesn't lead to a win, return nil
        ((unwinnable-cycle gamestate) ; either it's impossible to win, or
         nil) ; it's possible to win from an earlier position, return nil
        (t (cl-some (lambda (move) ; otherwise return the first non-losing move which leads
                      (find-good-moves (advance-gamestate gamestate move))) ; to a non-nil result
                    (non-losing-moves gamestate)))))

(defun make-initial-gamestate (orders)
  "Given an orders list, create initial gamestate"
  (list orders () 0))

```

---
Tags: code-golf
---


# Question
Title: Dihedral group D4 composition with custom labels
The dihedral group \\$D\_4\\$ is the symmetry group of the square, that is the moves that transform a square to itself via rotations and reflections. It consists of 8 elements: rotations by 0, 90, 180, and 270 degrees, and reflections across the horizontal, vertical, and two diagonal axes.

*The images are all from this lovely page by Larry Riddle.*

This challenge is about composing these moves: given two moves, output the move that's equivalent to doing them one after another. For instance, doing move 7 followed by move 4 is the same as doing move 5.

Note that switching the order to move 4 then move 7 produces move 6 instead.

The results are tabulated below; this is the Cayley table of the group \\$D\_4\\$. So for example, inputs \\$7, 4\\$ should produce output \\$5\\$.

\begin{array}{\*{20}{c}} {} & {\begin{array}{\*{20}{c}} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \end{array} } \\ {\begin{array}{\*{20}{c}} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ \end{array} } & {\boxed{\begin{array}{\*{20}{c}} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 4 & 1 & 8 & 7 & 5 & 6\\ 3 & 4 & 1 & 2 & 6 & 5 & 8 & 7\\ 4 & 1 & 2 & 3 & 7 & 8 & 6 & 5\\ 5 & 7 & 6 & 8 & 1 & 3 & 2 & 4\\ 6 & 8 & 5 & 7 & 3 & 1 & 4 & 2\\ 7 & 6 & 8 & 5 & 4 & 2 & 1 & 3\\ 8 & 5 & 7 & 6 & 2 & 4 & 3 & 1\\ \end{array} }} \\ \end{array}

**Challenge**

Your goal is to implement this operation in as few bytes as possible, but in addition to the code, **you also choose the labels** that represent the moves 1 through 8. The labels must be *8 distinct numbers from 0 to 255*, or the 8 one-byte characters their code points represent.

Your code will be given two of the labels from the 8 you've chosen, and must output the label that corresponds to their composition in the dihedral group \\$D\_4\\$.

**Example**

Say you've chosen the characters C, O, M, P, U, T, E, R for moves 1 through 8 respectively. Then, your code should implement this table.

\begin{array}{\*{20}{c}} {} & {\begin{array}{\*{20}{c}} \\, C \\, & \\, O \\, & M \\, & P \\, & U \\, & \\, T \\, & \\, E \\, & R \\, \\ \end{array} } \\ {\begin{array}{\*{20}{c}} C \\ O \\ M \\ P \\ U \\ T \\ E \\ R \\ \end{array} } & {\boxed{\begin{array}{\*{20}{c}} C & O & M & P & U & T & E & R \\ O & M & P & C & R & E & U & T\\ M & P & C & O & T & U & R & E\\ P & C & O & M & E & R & T & U\\ U & E & T & R & C & M & O & P\\ T & R & U & E & M & C & P & O\\ E & T & R & U & P & O & C & M\\ R & U & E & T & O & P & M & C\\ \end{array} }} \\ \end{array}

Given inputs E and P, you should output U. Your inputs will always be two of the letters C, O, M, P, U, T, E, R, and your output should always be one of these letters.

**Text table for copying**

```
1 2 3 4 5 6 7 8
2 3 4 1 8 7 5 6
3 4 1 2 6 5 8 7
4 1 2 3 7 8 6 5
5 7 6 8 1 3 2 4
6 8 5 7 3 1 4 2
7 6 8 5 4 2 1 3
8 5 7 6 2 4 3 1

```

# Answer
# Ruby, 18 bytes

```
->a,b{a+b*~0**a&7}

```

Ungolfed

```
->a,b{ (a+b*(-1)**a) % 8}
# for operator precedence reasons,
#-1 is represented as ~0 in the golfed version

```

Try it online!

Uses the following coding numbers 0 to 7

In order native to the code:

```
Native     Effect                    Codes per
Code                                 Question
0          rotate 0 anticlockwise    1C
1 /        flip in y=x               7E
2 /|       rotate 90 anticlockwise   2O
3 /|/      flip in x axis            5U
4 /|/|     rotate 180 anticlockwise  3M
5 /|/|/    flip in y=-x              8R
6 /|/|/|   rotate 270 anticlockwise  4P
7 /|/|/|/  flip in y axis            6T

```

In order per the question

```
Native     Effect                    Codes per
Code                                 Question
0          rotate 0 anticlockwise    1C
2 /|       rotate 90 anticlockwise   2O
4 /|/|     rotate 180 anticlockwise  3M
6 /|/|/|   rotate 270 anticlockwise  4P
3 /|/      flip in x axis            5U
7 /|/|/|/  flip in y axis            6T
1 /        flip in y=x               7E
5 /|/|/    flip in y=-x              8R

```

**Explanation**

`/` represents a flip in the line `y=x` and `|` represents a flip in the y axis.

It is possible to generate any of the symmetries of the group D4 by alternately flipping in these two lines For example `/` followed by `|` gives `/|` which is a rotation of 90 degrees anticlockwise.

The total number of consecutive flips gives a very convenient representation for arithmetic manipulation.

If the first move is a rotation, we can simply add the number of flips:

```
Rotate 90 degrees   +  Rotate 180 degrees = Rotate 270 degrees
/|                     /|/|                 /|/|/|

Rotate 90 degress   +  Flip in y=x        = Flip in x axis
/|                    /                     /|/

```

If the first move is a reflection, we find we have some identical reflections `/` and `|` symbols next to each other. As reflection is self inverse we can cancel out these flips one by one. So we need to subtract one move from the other

```
Flip in x axis     +  Flip in y=x        = Rotate 90 degrees
/|/                   /                    /|/ / (cancels to) /|

Flip in x axis     +  Rotate 90 degrees  = Flip in y=x
/|/                   /|                   /|/ /| (cancels to ) /

```
> 10 votes

# Answer
# Wolfram Language (Mathematica), 31 bytes

Using integers \\$0, 5, 2, 7, 1, 3, 6, 4\\$ as labels.

```
BitXor[##,2Mod[#,2]⌊#2/4⌋]&

```

Try it online!

## Explanation:

The Dihedral group \\$D\_4\\$ is isomorphic to the unitriangular matrix group of degree three over the field \\$\mathbb{F}\_2\\$:

$$D\_4 \cong U(3,2) := \left\\{\begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix} \mid a,b,c \in \mathbb{F}\_2\right\\}.$$

And we have

$$\begin{pmatrix} 1 & a\_1 & b\_1 \\ 0 & 1 & c\_1 \\ 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & a\_2 & b\_2 \\ 0 & 1 & c\_2 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & a\_1+a\_2 & b\_1+b\_2+a\_1c\_2 \\ 0 & 1 & c\_1+c\_2 \\ 0 & 0 & 1 \end{pmatrix},$$

which can easily be written in bitwise operations.
> 7 votes

# Answer
# Wolfram Language (Mathematica), 51 bytes

```
⌊#/4^IntegerDigits[#2,4,4]⌋~Mod~4~FromDigits~4&

```

Try it online!

Using labels `{228, 57, 78, 147, 27, 177, 198, 108}`.

These are `{3210, 0321, 1032, 2103, 0123, 2301, 3012, 1230}` in base 4. Fortunately, 256=4^4.

---

Lower-level implementation, also 51 bytes

```
Sum[4^i⌊#/4^⌊#2/4^i⌋~Mod~4⌋~Mod~4,{i,0,3}]&

```

Try it online!
> 5 votes

# Answer
# Python 2, 22 bytes

A port of my Mathematica answer. Using integers \\$0, 6, 1, 7, 2, 3, 5, 4\\$ as labels.

```
lambda a,b:a^b^a/2&b/4

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~26~~ ~~23~~ 21 bytes

```
lambda x,y:y+x*7**y&7

```

Try it online! Port of my answer to Cayley Table of the Dihedral Group \\$D\_3\\$. Edit: Saved 3 bytes thanks to @NieDzejkob. Saved 2 bytes thanks to @xnor for suggesting the `and` (rather than `xnor`) operator. Uses the following mapping:

```
 id | r1 | r2 | r3 | s0 | s1 | s2 | s3
----+----+----+----+----+----+----+----
 0  | 2  | 4  | 6  | 1  | 3  | 5  | 7

```
> 4 votes

# Answer
# TI-BASIC, 165 bytes

```
Ans→L₁:{.12345678,.23417865,.34126587,.41238756,.58671342,.67583124,.75862413,.86754231→L₂:For(I,1,8:10fPart(.1int(L₂(I)₁₀^(seq(X,X,1,8:List▶matr(Ans,[B]:If I=1:[B]→[A]:If I-1:augment([A],[B]→[A]:End:[A](L₁(1),L₁(2

```

Input is a list of length two in `Ans`.
Output is the number at the `(row, column)` index in the table.

There could be a better compression method which would save bytes, but I'll have to look into that.

**Examples:**

```
{1,2
           {1 2}
prgmCDGF1B
               2
{7,4
           {7 4}
prgmCDGF1B
               5

```

**Explanation:**
(Newlines have been added for readability.)

```
Ans→L₁                              ;store the input list into L₁
{.123456 ... →L₂                    ;store the compressed matrix into L₂
                                    ; (line shortened for brevity)
For(I,1,8                           ;loop 8 times
10fPart(.1int(L₂(I)₁₀^(seq(X,X,1,8  ;decompress the "I"-th column of the matrix
List▶matr(Ans,[B]                   ;convert the resulting list into a matrix column and
                                    ; then store it into the "[B]" matrix variable
If I=1                              ;if the loop has just started...
[B]→[A]                             ;then store this column into "[A]", another matrix
                                    ; variable
If I-1                              ;otherwise...
augment([A],[B]→[A]                 ;append this column onto "[A]"
End
[A](L₁(1),L₁(2                      ;get the index and keep it in "Ans"
                                    ;implicit print of "Ans"

```

Here's a **155 byte** solution, but it just hardcodes the matrix and gets the index.
I found it to be more boring, so I didn't make it my official submission:

```
Ans→L₁:[[1,2,3,4,5,6,7,8][2,3,4,1,8,7,5,6][3,4,1,2,6,5,8,7][4,1,2,3,7,8,6,5][5,7,6,8,1,3,2,4][6,8,5,7,3,1,4,2][7,6,8,5,4,2,1,3][8,5,7,6,2,4,3,1:Ans(L₁(1),L₁(2

```

---

**Note:** TI-BASIC is a tokenized language. Character count does ***not*** equal byte count.
> 3 votes

# Answer
# JavaScript (Node.js), ~~22~~ 17 bytes

```
(x,y)=>y+x*7**y&7

```

Try it online! Port of my answer to Cayley Table of the Dihedral Group \\$D\_3\\$ but golfed down using the suggestions on my Python answer. Uses the following mapping:

```
 id | r1 | r2 | r3 | s0 | s1 | s2 | s3
----+----+----+----+----+----+----+----
 0  | 2  | 4  | 6  | 1  | 3  | 5  | 7

```

Older versions of JavaScript can be supported in a number of ways for 22 bytes:

```
(x,y)=>(y&1?y-x:y+x)&7
(x,y)=>y-x*(y&1||-1)&7
(x,y)=>y+x*(y<<31|1)&7

```
> 3 votes

# Answer
# Jelly, 6 bytes

```
N⁹¡+%8

```

A dyadic Link accepting the first transform on the right and the second transform on the left which yields the composite transform.

Where the transforms are:

```
as in question:  1    2    3    4    5    6    7    8
transformation: id  90a  180  90c  hor  ver  +ve  -ve
  code's label:  0    2    4    6    1    5    7    3

```

**Try it online!** ...Or see the table mapped back onto the labels in the question.

(The arguments could be taken in the other order using the 6 byter, `_+Ḃ?%8`)

### How?

Each label is the length of a sequence of alternating `hor` and `+ve` transforms which is equivalent to the transform (e.g. `180` is equivalent to `hor, +ve, hor, +ve`).

The composition `A,B` is equivalent to the concatenation of the two equivalent sequences, and allows simplification to subtraction or addition modulo eight...

Using the question's `7, 4` example we have `+ve, 90c` which is:
`hor, +ve, hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve, hor, +ve`

...but since `hor, hor` is `id` we have:
`hor, +ve, hor, +ve, hor, +ve , +ve, hor, +ve, hor, +ve`

...and since `+ve, +ve` is `id` we have:
`hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve`

...and we can repeat these cancellations to:
`hor`
..equivalent to subtraction of the lengths (`7-6=1`).

When no cancellations are possible we are just adding the lengths (like `90a, 180` \\$\rightarrow\\$ `2+4=6` \\$\rightarrow\\$ `90c`).

Lastly, note that a sequence of length eight is `id` so we can take the resulting sequence length modulo eight.

```
N⁹¡+%8 - Link: B, A
  ¡    - repeat (applied to chain's left argument, B)...
 ⁹     - ...times: chain's right argument, A
N      - ...action: negate  ...i.e. B if A is even, otherwise -B
   +   - add (A)
    %8 - modulo eight

```

---

It's also 1 byte shorter than this implementation using lexicographical permutation indexes:

```
œ?@ƒ4Œ¿

```

...a monadic Link accepting `[first, second]`, with labels:

```
as in question:  1    2    3    4    5    6    7    8
transformation: id  90a  180  90c  hor  ver  +ve  -ve
  code's label:  1   10   17   19   24    8   15    6

```
> 3 votes

# Answer
# Rust, 16 bytes

```
|a,b|a^b^a/2&b/4

```

Try it online!

Port of alephalpha's Python answer. But shorter.
> 2 votes

# Answer
# Elm, ~~42 bytes~~ 19 bytes

```
\a b->and 7<|b+a*7^b

```

Port of the Neil's Node.js version

Try it online

**Previous version:**

```
\a b->and 7<|if and 1 a>0 then a-b else a+b

```
> 2 votes

# Answer
# Python, ~~82~~ 71 bytes

0-7
-11 bytes thanks to ASCII-only

```
lambda a,b:int("27pwpxvfcobhkyqu1wrun3nu1fih0x8svriq0",36)>>3*(a*8+b)&7

```

TIO
> 1 votes

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

```
a=>b=>a^b^a/2&b/4

```

Port of alpehalpha's Python answer.

Try it online!
> 0 votes

# Answer
# Scala, 161 bytes

Choosing **COMPUTER** as labels.

```
val m="0123456712307645230154763012675446570213574620316574310274651320"
val s="COMPUTER"
val l=s.zipWithIndex.toMap
def f(a: Char, b: Char)=s(m(l(a)*8+l(b))-48)

```

Try it online!
> 0 votes

# Answer
# Scala, 70 bytes

Choosing 0-7 native integers as labels.

Compressed the matrix into 32 byte ASCII string, each pair of numbers n0, n1 into 1 character c = n0 + 8\*n1 + 49. Starting from 49 to that we don't have \ in the encoded string.

```
(a:Int,b:Int)=>"9K]oB4h]K9Vh4BoVenAJne3<_X<AX_J3"(a*4+b/2)-49>>b%2*3&7

```

Try it online!
> 0 votes

# Answer
# Perl 6, 19 bytes

```
{($^x*7**$^y+$y)%8}

```

Port of Neil's Python solution.

Try it online!
> 0 votes

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