title: Is it a shuffle?

text:
# Question
Title: Is it a shuffle?
Yesterday I asked this question about riffle shuffles. It seems that yesterdays question was a bit too hard so this question is a related but much easier task.

Today you are asked to determine if a permutation is in fact a riffle shuffle. Our definition of riffle shuffle is adapted from our last question:

The first part of the shuffle is the divide. In the divide partition the deck of cards in two. The two subsections must be continuous, mutually exclusive and exhaustive. In the real world want to make your partition as close to even as possible, however in this challenge this is not a consideration, all partitions including ones that are degenerate (one partition is empty) are of equal consideration.

After they have been partitioned, the cards are spliced together in such a way that cards maintain their relative order *within the partition they are a member of*. For example, if card **A** is before card **B** in the deck and cards **A** and **B** are in the same partition, card **A** must be before card **B** in the final result, even if the number of cards between them has increased. If **A** and **B** are in different partitions, they can be in any order, regardless of their starting order, in the final result.

Each riffle shuffle can then be viewed as a permutation of the original deck of cards. For example the permutation

```
1,2,3 -> 1,3,2

```

is a riffle shuffle. If you split the deck like so

```
1, 2 | 3

```

we see that every card in `1,3,2` has the same relative order to every other card in it's partition. `2` is still after `1`.

On the other hand the following permutation is *not* a riffle shuffle.

```
1,2,3 -> 3,2,1

```

We can see this because for all the two (non-trivial) partitions

```
1, 2 | 3
1 | 2, 3

```

there is a pair of cards that do not maintain their relative orderings. In the first partition `1` and `2` change their ordering, while in the second partition `2` and `3` change their ordering.

## Task

Given a permutation via any reasonable method, determine if it represents a valid riffle shuffle. You should output two distinct constant values one for "Yes, this is a riffle shuffle" and one for "No, this is not a riffle shuffle".

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

## Test Cases

```
1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False

```

# Answer
> 8 votes
# JavaScript (ES6), 47 bytes

Takes input as an array of integers. Returns a boolean.

```
([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

```

### Test cases

```
let f =

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

;[
  [1,3,2      ],  // -> True
  [3,2,1      ],  // -> False
  [3,1,2,4    ],  // -> True
  [2,3,4,1    ],  // -> True
  [4,3,2,1    ],  // -> False
  [1,2,3,4,5  ],  // -> True
  [1,2,5,4,3  ],  // -> False
  [3,1,4,2,5  ],  // -> True
  [2,3,6,1,4,5]   // -> False
]
.forEach(a => console.log(JSON.stringify(a) + ' -> ' + f(a)))
```

### How?

The input array **A** is a valid riffle shuffle if it consists of at most two distinct interlaced sequences of consecutive integers.

The challenge rules specify that we're given a *permutation* of **\[1...N\]**. So we don't need to additionally check that the sorted union of these sequences actually results in such a range.

We use a counter **x** initialized to **A\[0\]** and a counter **y** initially undefined.

For each entry **z** in **A**, starting with the 2nd one:

* We check whether **z** is equal to either **x+1** or **y+1**. If yes, we increment the corresponding counter.
* Else: if **y** is still undefined, we initialize it to **z**.
* Else: we make the test fail.

# Answer
> 6 votes
# Haskell, 41 bytes

```
n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l

```

Try it online!

Checks if the list concatenated to itself contains the numbers `0..n-1` in order as a subsequence.

# Answer
> 5 votes
# Haskell, 43 bytes

`s` takes a list of integers as in the OP examples and returns a `Bool`.

```
s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter

```

Try it online!

# How it works

* The list comprehension tries each element `x` of `p` in turn and checks if it can be the first element of the second partition of the shuffle. Then `or` returns `True` if any of the checks were `True`.
* The comprehension does this by partitioning (with `filter`) `p` into elements smaller and larger than (or equal to) `x`, concatenating, and checking if the resulting list is `[1..length p]`, i.e. the elements in order.
* The check for whether the resulting list is `[1..length p]` is done by seeing if the result is strictly smaller than the infinite list `[1..] == [1,2,3,etc.]`, which gives the same result for any permutation.

# Answer
> 5 votes
# Jelly, ~~13~~ 6 bytes

```
ỤIṢḊRẠ

```

Try it online!

### Alternate version, postdates challenge, 5 bytes

```
Ụ>ƝSỊ

```

Try it online!

### How it works

```
ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])

Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.

```

# Answer
> 5 votes
# Python 2, 39 bytes

```
l=input()
n=0
for x in l*2:n+=n==x
l[n]

```

Try it online!

Takes the list 0-indexed and outputs via exit code.

# Answer
> 4 votes
# Brachylog, 9 bytes

```
o~cĊ⟨⊆⊇⟩?

```

Try it online!

The predicate succeeds if the input represents a riffle shuffle and fails if it does not, meaning among other things that if the predicate is run as an entire program success will print `true.` and failure will print `false.`. Input is taken as a list of any sorts of items and interprets it as representing a permutation of itself sorted.

```
   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.

```

I feel like there's something in the spirit of `⊆ᵐ` which should work in the place of the four-byte "sandwich" construct `⟨⊆⊇⟩`.

# Answer
> 3 votes
# Python 2, ~~75~~ ~~60~~ 47 bytes

thanks to Dennis for -13 bytes

```
x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q

```

Try it online!

Output is via exit code.

# Answer
> 2 votes
# Ruby, 35 bytes

```
->l{l.any?{|a|l&[*1..a]|l==l.sort}}

```

Try it online!

## How?

* `l & [*1..a] | l` applies an intersection and then an union: first get the elements of `l` that are `<=a` and then add the remaining elements of `l` without changing the order. If a is the number we are looking for, then this operation is the same as sorting `l`.

# Answer
> 2 votes
# Clean, ~~56~~ 55 bytes

```
import StdEnv
?l=any(\e=sortBy(\a b=a<e&&b>=e)l<[1..])l

```

Try it online!

# Answer
> 2 votes
## Pyth, 5 bytes

```
}SQy+

```

**Test suite**

```
}SQy+

    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted

```

Checks whether the doubled input list contains a sorted version of itself as a subsequence.

Thanks to Erik the Outgolfer for 1 byte taking better advantage of implicit input with `+QQ` rather than `*2Q`.

# Answer
> 1 votes
# Pyth, 9 bytes

```
!t-.+xLQS

```

**Test suite.**

Saved 3 bytes thanks to isaacg.

# Pyth, 14 bytes

```
}SQm.nS.Tcd2./

```

**Try it here!** or **Verify all the test cases.**

Outputs `True` and `False` for riffle-shuffle and non-riffle-shuffle respectively.

### How?

```
}SQm.nS.Tcd2./ ~ Full program. Reads input from STDIN and outputs to STDOUT.

            ./ ~ Return all divisions of the input into disjoint substrings (partition).
   m           ~ Map over the above using a variable d.
         cd2   ~ Chop d into two-element lists.
       .T      ~ Justified transpose, ignoring absences.
      S        ~ Sort (lexicographically).
    .n         ~ Deep-flatten.
}              ~ Check if the above contains...
 SQ            ~ The sorted input.

```

# Answer
> 0 votes
# Husk, 7 bytes

```
±§#OoṖD

```

**Test suite!**

# Answer
> 0 votes
# Perl, 28 bytes

Includes `+1` for `a`

Input on STDIN, 1 based

```
perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"

```

Uses xnor's algorithm

# Answer
> 0 votes
# C (gcc), 61 bytes

```
a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}

```

Try it online!

---
Tags: code-golf, decision-problem, combinatorics, card-games
---


title: Implement MENACE

text:
# Question
Title: Implement MENACE
# Background

MENACE (**M**achine **E**ducable **N**oughts **A**nd **C**rosses **E**ngine) is a rudimentary shallow machine learning algorithm for the game Noughts and Crosses, created by British computer scientist Donald Michie in the 1960s. It was originally implemented with 304 matchboxes, each labelled with a board position and containing coloured beads (with one of nine colours, representing possible moves). Michie calculated that these 304 matchboxes were enough for every combination of moves on the board.

The more mathematical among you may realise that there are actually 19,683 possible combinations of Noughts, Crosses and Blanks on a N&C board; however, he calculated ways to cut down on this number (to speed up the algorithm, and likely to cut down on matchboxes!). Firstly, he removed all none-possible moves, such as:

```
-------
|X|0|X|
| |0| |
|X|X| |
-------

```

(two noughts and four crosses)

Next, he compensated for rotations. For instance, if on the matchbox we see:

```
-------
| |0|0|
|X| |X|
| |0| |
-------

```

we can use the same box for

```
-------
| |X| |
|0| |0|
| |X|0|
-------

```

Therefore, the aforementioned coloured beads represent relative positions, not absolute ones. For instance, if we said that a red bead meant top-left, then we'd take a look at the image on the top of the box and see:

```
-------
| |0|0|
|X| |X|
| |0| |
-------

```

so we'd know that in the case that this is the board, then the red bead would mean:

```
-------
|R|0|0|
|X| |X|
| |0| |
-------

```

But if this is the board:

```
-------
| |X| |
|0| |0|
| |X|0|
-------

```

the red bead would mean

```
-------
| |X|R|
|0| |0|
| |X|0|
-------

```

These transformations applied for rotations and inverting (in all directions, including diagonal). Once again, you only need to save each matchbox once this way: do not make separate virtual boxes for each transformation!

Another simplification Michie made was to make sure the computer goes first. This way, he could remove all first-level moves, removing about a fifth of the remaining boxes. Finally, he removed all game-ending boxes (as no further 'contents' or moves were required on these steps).

Right, now onto the algorithm itself (it's very simple):

1. First, decide on what the colours of the beads represent. You'll need 9 colours to represent each of the spaces on the board.
2. At the start of the game, each of the 304 matchboxes contains beads. While the beads are of random colour (so duplicates are fine), they should be possible moves (so if the board state image depicts an 'O' in the middle-right, then you can't use the bead that represents the middle-right).
3. Every time it is MENACE's (X) turn, find the matchbox with the current board position (or some transformation of it) printed onto it.
4. Open the matchbox, and choose any bead in there at random.
5. Find how the board status has been transformed to get to the image on the matchbox (e.g rotated 90deg anticlockwise). Then, apply that transformation to the bead (e.g top-left becomes left-left).
6. Place an X in that square. Remove the selected bead from the matchbox. If the box is left empty as a result, put three random (possible) beads into the box, and pick one of them for the move.
7. Repeat 3-6 until the game is over.
8. If MENACE won the game, go back through every matchbox MENACE took. Then, trace back what colour bead it used on that move. Put two of that colour of bead into the box (so that there is the original bead + one more, thereby increasing the likelyhood of MENACE making that move next time it gets to that position)
9. If MENACE lost the game, do nothing (**don't** replace the beads it took out).
10. If MENACE drew the game, then replace the bead it used in each of its moves, but don't add an extra one, so that you're left with what you started.

This leaves us with an algorithm that is very simple, but difficult to implement. This forms the basis of your challenge.

*If you're still confused, see http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/ \- it's what I read when I first learned about this algorithm*

# Challenge

Play a game of Tic-Tac-Toe with the computer. At each step, output the contents of all of the matchboxes.

## Inputs

* At the start of the program a number, saying how many games you want to play against MENACE
* Then, after MENACE's first turn, you input your move as a two character string, the first letter being "L", "R", or "M" (left, right or middle) referring to the Y axis. Then you input another letter (again, "L", "R", or "M"), this time referring to the X axis. Repeat for all moves and games.

## Outputs

* At the start of each new game, output "new game".
* After each move by the player, output the board in any reasonable format. It doesn't need to look pretty (e.g an array of arrays representing the positions of the board is fine).
* After each move by the player, MENACE should make a move. Output the board after MENACE's move
* After each game, output the contents of all 304 matchboxes. Beads can be represented by a letter, name of a colour, character or whatever **string or integer** you like (no pointers, anonymous functions, etc).

# Rules

1. This is , so shortest answer in bytes wins.
2. I must be able to input moves after seeing MENACE's response. No 'pass all of your moves into this function, and watch how the game plays out'.
3. The board must be cleared between games.
4. The matchboxes must *not* be cleared between games (this would reset the machine learning)
5. You must have 304 matchboxes. Anyone can implement this algorithm with all 19,683 matchboxes, but the learning is slow (as it requires *lots* of games to get all of them with useful contents).
6. The output can be in any reasonable format, and input can be taken as per PPCG standards (as long as it complies with rule 2). If you need to adjust the input format (as described in the '**Input**' section) then it's OK as long as it makes sense.
7. A game ends when a player wins (by getting three in a row diagonally, horizontally or vertically) or if there is a draw (the board is full and there is no winner)
8. While MENACE needs to make possible moves (and only have possible beads inside each matchbox), for the sake of the challenge you don't need to validate the input of the user. If they type in something wrong, your program can do whatever (go completely crazy, throw error, etc.) - you can assume that the input is correct.

# Answer
> 3 votes
# , 839 bytes

```
options(max.print=1e5)
s=colSums
r=rowSums
m=matrix
a=array
y=apply
S=sum
p=sample
b=m(rep(i<-1:(K=3^9),e=9)%/%(E=3^(8:0))%%3,c(9,K))
V=a(1:9,c(3,3,8))
V[,,2:4]=c(V[x<-3:1,,1],V[,x,1],V[x,x,1])
V[,,5:8]=y(V[,,1:4],3,t)
d=aperm(a(b[c(V),],c(9,8,K)),c(1,3,2))
v=m(V,9)
g=y(m(match(e<-y(d*E,2:3,S),i),,8),1,min)
g[K]=K
G=9-y(t(e==g)*8:1,2,max)
h=s(a(c(b,d[,,5],b[c(1,5,9,3,5,7,1:3),]),c(3,3,K,3))*3^(0:2))
k=r(s(h==13))>0
l=r(s(h==26))>0
o=s(b>0)
M=b
M[M==0]=-1
repeat{A=b[,t<-K]
z=j=c();B=1
repeat{if(S(pmax(-M[,t],0))<1)M[p(9,pmin(3,S(x)),,x<-M[,t]<1),t]=-1
z=c(z,u<-p(9,1,,pmax(-M[,t],0)))
j=c(j,t)
A[v[,G[B]][u]]=1
print(m(A,3))
if(k[B<-S(A*E)]||o[B]==9)break
A[ceiling((utf8ToInt(readline())-76)/5)%*%c(1,3)+1]=2
if(l[B<-S(A*E)])break
t=g[B]}
M[x]=M[x<-cbind(z,j)]-k[B]+l[B]
print(a(M[,g==seq(g)&!k&!l&s(b==1)==s(b==2)&o<8],c(3,3,304)))}

```

Try it online!

Quite a long answer, but this wasn't a straightforward challenge. The TIO link here will fail because it expects interactive input. Here's a version that plays against a second, random player who just picks a spot at random. The output for this second version is just the winner (1, 2 or 0 for a draw.) Matchboxes are initialised for all board positions, but only used for the 304 per the spec. They're implemented as copies of the board with negative numbers to indicate the number of beads on each position. I experimented with a list of vectors per the original spec, but it was less intuitive.

This is a less golfed version with comments (but still short variable names). Note that it doesn't print the matchboxes out because they're very long. It can implement an interactive player 2, a random player 2 or the same matchbox strategy for player 2.

```
auto = 1 # 1 = Random player 2, 2 = Player 2 uses learning strategy
         # 0 for interactive
print_board <- function(board) {
  cat(apply(matrix(c(".", "X", "O")[board + 1], 3), 1, paste, collapse = ""), "", sep = "\n")
}
E = 3 ^ (8:0) # Number of possible arrangements of board
              # ignoring rotations etc.
# Make all possible boards
b = matrix(rep(1:3 ^ 9, e = 9) %/% E %% 3, c(9, 3 ^ 9))
# Define the eight possible rotation/inversion matrices
V = array(1:9, c(3, 3, 8))
V[, , 2:4] = c(V[x <- 3:1, , 1], V[, x, 1], V[x, x, 1])
V[, , 5:8] = apply(V[, , 1:4], 3, t)
# Create eight copies of the 19683 boards with each transformation
d = aperm(array(b[c(V), ], c(9, 8, 3 ^ 9)), c(1, 3, 2))
v = matrix(V, 9)
# Create reverse transformations (which are the same except for rotation)
w = v[, c(1:5, 7, 6, 8)]
# Find the sums of each transformation using base 3
e = apply(d * E, 2:3, sum)
# Find the lowest possible sum for each board's transformed versions
# This will be the one used for the matchboxes
f = matrix(match(e, 1:3 ^ 9), , 8)
g = apply(f, 1, min)
# Store which transformation was necessary to convert the lowest board
# into this one
G = 9 - apply(t(e == g) * 8:1, 2, max)
# Work out which boards have 3-in-a-row
h = colSums(array(c(b, d[, , 5], b[c(1, 5, 9, 3, 5, 7, 1:3), ]), c(3, 3, 3 ^ 9, 3)) * 3 ^ (0:2))
k = rowSums(colSums(h == 13)) > 0 # player 1 wins
l = rowSums(colSums(h == 26)) > 0 # player 2 wins
# Store how many cells are filled
o = colSums(b > 0)
# Create matchboxes. These contain the actual board configuration, but
# instead of zeroes for blanks have a minus number. This is initially -1,
# but will ultimately represent the number of beads for that spot on the
# board.
M = b
M[M == 0] = -1
repeat {
  # Initialise board and storage of moves and intermediate board positions
  A = b[, t <- 3 ^ 9]
  z = j = c()
  C = 1
  # If we're automating player 2 also, initialise its storage
  if (auto) {
    Z = J = c()
  }
  repeat {
    # If the current board's matchbox is empty, put up to three more beads
    # back in
    if (sum(pmax(-M[, t], 0)) == 0) {
      M[sample(9, pmin(3, sum(x)), , x <- M[, t] == 0), t] = -1
    }
    # Take out a bead from the matchbox
    u = sample(9, 1, , pmax(-M[, t], 0))
    # Mark the bead as taken out
    M[u, t] = M[u, t] + 1
    # Store the bead and board position in the chain for this game
    z = c(z, u)
    j = c(j, t)
    # Mark the spot on the board
    A[v[, C][u]] = 1
    # Print the board
    if (!auto) print_board(matrix(A, 3))
    # Check if  player 1 has won or board is full
    if (k[B <- sum(A * E)] || o[B] == 9) break
    if (auto) {
      # Repeat for player 2 if we're automating its moves
      # Note if auto == 1 then we pick at random
      # If auto == 2 we use the same algorithm as player 1
      D = g[B]
      if (sum(pmax(-M[, D], 0)) == 0) {
        M[sample(9, pmin(3, sum(x)), , x <- M[, D] == 0), D] = -1
      }
      U = sample(9, 1, , if (auto == 1) M[, D] <= 0 else pmax(-M[, D], 0))
      Z = c(Z, U)
      J = c(J, D)
      A[v[, G[B]][U]] = 2
    } else {
      cat(
        "Please enter move (LMR for top/middle/bottom row and\nLMR for left/middle/right column, e.g. MR:"
      )
      repeat {
        # Convert LMR into numbers
        q = ceiling((utf8ToInt(readline()) - 76) / 5)
        if (length(q) != 2)
          stop("Finished")
        if (all(q %in% 0:2) && A[q %*% c(1, 3) + 1] == 0) {
          break
        } else {
          message("Invalid input, please try again")
        }
      }
      A[q %*% c(1, 3) + 1] = 2
    }
    if (l[B <- sum(A * E)])
      break
    # Player 2 has won
    t = g[B]
    C = G[B]
  }
  if (auto) {
    cat(c("D", 1:2)[1 + k[B] + 2 * l[B]])
  } else {
    cat("Outcome:", c("Draw", sprintf("Player %d wins", 1:2))[1 + k[B] + 2 * l[B]], "\n")
  }
  # Add beads back to matchbox
  M[x] = M[x <- cbind(z, j)] - k[B] - 1 + l[B]
  if (auto)
    M[x] = M[x <- cbind(Z, J)] - l[B] - 1 + k[B]
}

```

---
Tags: code-golf, board-game, ai-player, interactive
---


title: Is it a valid penalty shoot-out prefix?

text:
# Question
Title: Is it a valid penalty shoot-out prefix?
In association football (also known as soccer), a penalty shoot-out is the second tie-breaker measure that may be used in a match which can't end in a tie, after extra time (i.e. association football overtime).

In a penalty shoot-out, the main referee tosses a coin to determine at which goal the shoot-out happens, and then tosses another coin to determine which team starts first. However, the only thing relevant to this challenge is what happens then, described below.

Each team has 5 penalties available at start, and the penalty score is 0-0. If, at any point, a team's remaining penalties aren't enough to change the currently winning team, the shoot-out stops.

If there are no remaining penalties, but both teams' points are equal, an additional penalty is granted to both teams. This is repeated until the points aren't equal.

After the shoot-out stops, the team with the largest penalty score wins the game.

# Challenge

Your challenge is, given two lists `A` and `B` representing which penalties team A and team B scored respectively, to determine if they represent a valid penalty shoot-out. A shoot-out is valid if the state represented by the input can be reached, regardless of whether the winning team can be determined. Note that you possibly have to test for both scenarios (Team A starting, Team B starting), since, if the state described in the input is reachable for at least one scenario, the input is valid. If the lists' lengths are different, the team represented by the longer one starts first (it can only have one more element than the other one, and the shorter list's team can't start, since then the longer list's team would shoot two penalties in a row, as the shorter list will be prematurely depleted).

# Detailed examples

*You can skip to the **Rules** section below, these are only to help solving the challenge.*

Suppose you get this shoot-out as input, where `-` means no goal was scored and `X` means a goal was scored (it's invalid):

```
Team A: - X X X X
Team B: - - - - X

Assuming team A starts first:

Team A: - (0 - 0) (max possible score 4 - 5)
Team B: - (0 - 0) (max possible score 4 - 4)
Team A: X (1 - 0) (max possible score 4 - 4)
Team B: - (1 - 0) (max possible score 4 - 3)
Team A: X (2 - 0) (max possible score 4 - 3)
Team B: - (2 - 0) (max possible score 4 - 2)
Team A: X (3 - 0) (max possible score 4 - 2)
Team A already has a higher score than B could ever have, but the input hasn't
ended yet, so it's invalid if team A is first.

Assuming team B starts first:

Team B: - (0 - 0) (max possible score 5 - 4)
Team A: - (0 - 0) (max possible score 4 - 4)
Team B: - (0 - 0) (max possible score 4 - 3)
Team A: X (1 - 0) (max possible score 4 - 3)
Team B: - (1 - 0) (max possible score 4 - 2)
Team A: X (2 - 0) (max possible score 4 - 2)
Team B: - (2 - 0) (max possible score 4 - 1)
Team A already has a higher score than B could ever have, but the input hasn't
ended yet, so it's invalid if team B stars first.

The input is invalid no matter which team starts first, so it's considered
invalid.

```

On the contrary, here is a valid example:

```
Team A: X X X
Team B: - - -

Assuming team A starts first:

Team A: X (1 - 0) (max possible score 5 - 5)
Team B: - (1 - 0) (max possible score 5 - 4)
Team A: X (2 - 0) (max possible score 5 - 4)
Team B: - (2 - 0) (max possible score 5 - 3)
Team A: X (3 - 0) (max possible score 5 - 3)
Team B: - (3 - 0) (max possible score 5 - 2)
It can be determined that team A wins, however the input has ended, so it's
valid if team A starts first. Therefore, the input is valid.

```

Another example, this time with extra penalties:

```
Team A: X - X - - - X -
Team B: - X X - - - X X

Assuming team A starts first:

Team A: X (1 - 0) (max possible score 5 - 5)
Team B: - (1 - 0) (max possible score 5 - 4)
Team A: - (1 - 0) (max possible score 4 - 4)
Team B: X (1 - 1) (max possible score 4 - 4)
Team A: X (2 - 1) (max possible score 4 - 4)
Team B: X (2 - 2) (max possible score 4 - 4)
Team A: - (2 - 2) (max possible score 3 - 4)
Team B: - (2 - 2) (max possible score 3 - 3)
Team A: - (2 - 2) (max possible score 2 - 3)
Team B: - (2 - 2) (max possible score 2 - 2)
First 5 penalties result in a tie, so we move on to extra penalties.
Team A: -, Team B: - (2 - 2)
Team A: X, Team B: X (3 - 3)
Team A: -, Team B: X (3 - 4)
It can be determined that team B wins, however the input has ended, so it's
valid if team A starts first. Therefore, the input is valid.

```

Here is a valid input where it's too early to determine the winner:

```
Team A: X X - -
Team B: - X - X

Assuming team A starts first:

Team A: X (1 - 0) (max possible score 5 - 5)
Team B: - (1 - 0) (max possible score 5 - 4)
Team A: X (2 - 0) (max possible score 5 - 4)
Team B: X (2 - 1) (max possible score 5 - 4)
Team A: - (2 - 1) (max possible score 4 - 4)
Team B: - (2 - 1) (max possible score 4 - 3)
Team A: - (2 - 1) (max possible score 3 - 3)
Team B: X (2 - 2) (max possible score 3 - 3)
The input has ended before the winner can be determined, so it's valid if team A
starts first. Therefore, the input is valid.

```

Finally, here is an input where the lists' lengths differ:

```
Team A: - - -
Team B: X X - X

Since team B shot more penalties, it starts first:

Team B: X (0 - 1) (max possible score 5 - 5)
Team A: - (0 - 1) (max possible score 4 - 5)
Team B: X (0 - 2) (max possible score 4 - 5)
Team A: - (0 - 2) (max possible score 3 - 5)
Team B: - (0 - 2) (max possible score 3 - 4)
Team A: - (0 - 2) (max possible score 2 - 4)
Team B: X (0 - 3) (max possible score 2 - 4)
It can be determined that team B wins, however the input has ended, so it's
valid.

```

# Rules

* The team that shoots first can be either A or B, you can't assume one will always shoot first.
* The lists will either have the same length, or their lengths will differ by one.
* You may choose any two distinct and consistent values to represent scored/unscored penalties.
* The lists can also be represented as integers converted from bijective base 2, strings or your language's native list format. If a bijective base 2 format is chosen, the input rules apply to the numbers converted to bijective base 2 (so digits `1` and `2` can either mean scored and unscored or unscored and scored respectively). **Regular binary is not allowed**, as one can't determine the presence of leading zeroes in the intended binary representation.
* This is , so the shortest solution wins. However, please don't be discouraged from answering even if it seems like your language can't "beat the specialized ones".

# Test cases

In these test cases, a `0` will represent a no-goal, and a `1` will represent a goal.

Format:

```
[Team A], [Team B]

```

Valid inputs:

```
[], []
[0], [0]
[0], [1]
[1], [1]
[0], []
[1, 1, 1, 1], [0, 0, 1, 1]
[0, 1, 1, 1, 1], [0, 1, 1, 0]
[0, 0, 0, 0, 1], [0, 0, 0, 1, 0]
[0, 0, 0, 0, 1], [0, 0, 0, 1]
[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1]
[0, 1, 1, 1, 1], [0, 1, 1, 0, 1]
[1, 1, 1], [0, 0, 0]
[1, 1, 1, 1], [0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

```

Invalid inputs:

```
[0, 1, 1, 1, 1], [0, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1]
[1, 1, 1, 0], [0, 0, 0]
[1, 1, 1, 1], [0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 1], [0, 1, 0, 1, 0, 1]
[0, 0, 0, 0, 1], [0, 1, 1, 1, 0]

```

# Answer
> 3 votes
# JavaScript (ES6),  ~~117 112~~  109 bytes

Takes input as `(a)(b)`, using \\$1\\$ for unscored and \\$2\\$ for scored. Returns \\$0\\$ or \\$1\\$.

```
a=>b=>!(g=(a,b,P=Q=i=5)=>(p=a[5-i])|(q=b[5-i])&&(--i<0?P-Q:P-Q>i|Q+q-P-p>i&p<2)|g(a,b,P+p,Q+=q))(a,b)|!g(b,a)

```

Try it online!

### Commented

```
a => b =>                   // given a[] and b[]
  !(g = (                   // g is a recursive function taking:
      a,                    //   the results a[] of the team that plays first
      b,                    //   the results b[] of the team that plays second
      P =                   //   the cumulated goals P of the 1st team (relative value)
      Q =                   //   the cumulated goals Q of the 2nd team (relative value)
      i = 5                 //   a counter i
    ) =>                    // and returning a truthy value if something goes wrong
      (p = a[5 - i]) |      // if either the first team
      (q = b[5 - i]) && (   // or the second team is playing this round:
        --i < 0 ?           //   decrement i; if we've played more than 5 penalties:
          P - Q             //     do we already have a goal difference?
        :                   //   else:
          P - Q > i |       //     was the 1st team already guaranteed to win?
          Q + q - P - p > i //     or is the 2nd team now guaranteed to win
          & p < 2           //     while the 1st team failed its last attempt?
      ) |                   //
      g(                    //   do a recursive call:
        a, b,               //     pass a[] and b[] unchanged
        P + p,              //     update P
        Q += q              //     update Q
      )                     //   end of recursive call
  )(a, b) |                 // try g(a, b)
  !g(b, a)                  // try g(b, a); return 1 if at least one of them is falsy

```

# Answer
> 2 votes
# Python 2, ~~176~~ ~~169~~ ~~171~~ 169 bytes

*-2 bytes thanks to @Kevin Cruijssen*

```
exec"h=lambda a,b,m:m-%s/2>abs(sum(a)-sum(b));f=lambda a,b:a[5#==b[5#and h(a[:5],b[:5],6)if %s>10else h(a,b,7)and h(a[#,b[#,6)".replace("#",":~-%s/2]")%(("len(a+b)",)*6)

```

Try it online! (Including some extra test cases not listed above.)

Creates a function `f` that takes two arguments (the two lists of scored/unscored penalties) and returns `True` if the scores are possibly valid and `False` otherwise.

**Partial explanation:**

~~First of all, the `exec` construction is just a way to save a few bytes by not having to repeat the expression `len(a+b)` more than once. The above piece of code is equivalent to the following:~~

~~Update: the new and improved answer is the same byte count with or without `exec` trickery, so in the interests of simplicity I have removed it.~~

Update 2: The new bugfixed version includes even more string compression via substitution and `exec`. Yes, I use `%` formatting and a `.replace` on the same string. The code above is equivalent to:

```
h=lambda a,b,m:m-len(a+b)/2>abs(sum(a)-sum(b))
f=lambda a,b:a[5:(len(a+b)-1)/2]==b[5:~-len(a+b)/2]and h(a[:5],b[:5],6)if len(a+b)>10else h(a,b,7)and h(a[:(~-len(a+b)/2],b[:(len(a+b)-1)/2],6)

```

The main idea of this answer is to frame the question in terms of "half-points": each successful kick is a half-point and each failed one is a negative half-point. For a set of scores with length \\$\<=5\\$ to be continuable (`not len(a+b)>10`), the total number of kicks left must have been greater than or equal to the half-point margin between the two teams. When one team has kicked an extra time, a half-point must be subtracted from the margin for various reasons, so this can be simplified by integer-dividing both sides of the equation by two. This is the function `h` in the code (with the argument `m` equal to 6).

However, to be a valid set of scores, an input need not be strictly continuable, but it must have been continuable before the last kick to have been made. This condition is equivalent to saying that it must 1) have been continuable the last time both sides had kicked the same number of times and 2) currently be within two half-points of being continuable — which is where the final argument to `h` comes in: `h(a[:~-len(a+b)/2],b[:~-len(a+b)/2],6)` tests condition 1) and `h(a,b,7)` (the `7` representing an extra two allowable half-points in the margin) tests condition 2).

The case where each team has kicked a maximum of five times has thus been settled. (Explanation to be continued for the other case.)

In terms of low-level golfing, I'm doubt there's too much to shave off, but algorithmically it could probably be done quite a bit more simply.

# Answer
> 1 votes
# Jelly, ~~62~~ ~~54~~ 49 bytes

```
ṫ⁵Ṗm2¬Ạ
N§ỤḢƊ¦LÞṚZFÄµ12R:2U_ṁḣ⁵ṫ-N<Ø.ẠaÇoL<3
ṚÇoÇ

```

Try it online!

```
ṫ⁵Ṗm2¬Ạ # helper function to determine whether
        # even indices at or beyond 10 are zero
ṫ⁵      # tail - take every item from 10
  Ṗ     # remove last item
   m2   # take every second item
     ¬  # logical not, will return 1 for an empty list
      Ạ # all
# function to create cumulative score
# difference and check values
N§ỤḢƊ¦    # negate scores for team with lower score
          # (or one of them if both same score)
  LÞṚ     # sort by length, longest first
  ZF      # transpose lists and flatten
  Ä       # cumulative sum
  µ       # this cumulative score difference (CSD)
          # now becomes left value
  12R:2U_ # subtract cumulative score difference from
          # 6,5,5,4,4,3,3,2,2,1
  ṁḣ⁵     # shorten to be no longer than 10 items
          # and no longer than CSD
  ṫ-N<Ø.Ạ # check last two values are greater than 0,-1
  aÇ      # check that helper function also TRUE
  oL<3    # handle very short scores
# main link that calls the above for scores in either order
ṚÇoÇ

```

Note the footer code at tio is just to handle multiple test cases and print outputs against inputs.

Thanks to @EriktheOutgolfer for golfing off 8 bytes

# Answer
> 0 votes
# Perl 6, 123 bytes

```
{all map {@^b>@^a||[R,](map {abs(($+=$_)-++$ %2/2)>(5-++$ /2 max++$ %2)},flat roundrobin @a,-<<@b).skip.any},@^a,@^b,@b,@a}

```

Try it online!

Returns falsey for valid shoot-outs, truthy for invalid ones.

### Explanation

```
# Check whether block returns true (invalid shoot-out) for arguments (a, b) and (b, a)
{all map {...},@^a,@^b,@b,@a}
# Return true (invalid) if array b is longer than a
@^b>@^a||
# Return true (invalid) if any except the last value is true (shoot-out stopped)
[R,](...).skip.any
# Map values from a and negated b, interleaved
map {...},flat roundrobin @a,-<<@b
# Shoot out stopped?
abs(($+=$_)-++$ %2/2)>(5-++$ /2 max++$ %2)
    #     # Accumulator
           #        # Subtract 0.5 for first team
                      #                  # Sequence 4.5 4 3.5 3 2.5 2 1.5 1 1 0 1 0 1 0

```

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


title: Can my 4-note music box play that song?

text:
# Question
Title: Can my 4-note music box play that song?
I have a crank-operated music box that can play a series of four notes. When I turn the crank, it plucks one of four strings, depending on the position of the crank and the direction of the turn. When the crank is turned due north, the box (with its strings numbered 1 through 4) looks like this:

```
1  |  2
   |
   O

4     3

```

From there, I can turn the crank clockwise to pluck the #2 string and point the crank east:

```
1     2

   O---

4     3

```

Alternatively, I could have also turned the crank counterclockwise from north to play the #1 string and end with a crank pointing west:

```
1     2

---O

4     3

```

At any given time, then, the box can play one of two notes: the next note available in the clockwise direction or the next note in the counterclockwise direction.

# Challenge

Your challenge is to write a program or function that accepts a non-empty string of note values (i.e., numerals `1` through `4`) and determine if it is ever possible to play that sequence of notes on the music box. Produce a truthy or falsy result to indicate the playability or non-playability of the input.

Some notes:

* The input makes no assumptions about initial start position. The inputs `214` (starting east and moving strictly counterclockwise) and `234` (starting north and moving strictly clockwise) and both valid.
* The crank may move freely in either direction after each note. A series of the same note is possible (e.g., `33333`) by moving back and forth across one string. The series `1221441` is perfectly playable (starting west, moving clockwise two steps, then counterclockwise three steps, then clockwise two steps).

# Samples

Some `true` cases:

```
1
1234
1221
3333
143332
22234
2234
22214
1221441
41233

```

Some `false` cases:

```
13     (note 3 is never available after note 1)
1224   (after `122`, the crank must be north, so 4 is not playable)
121    (after `12` the crank is east; 1 is not playable)
12221  (as above, after `1222` the crank is east)
43221

```

# Answer
# Pyth, ~~30~~ 27 bytes

```
f!-aVJ.u%-ysYN8zTtJ,1 7cR2T

```

Here's the idea:

```
 1.5  1  0.5

  2       0

 2.5  3  3.5

```

The crank is always at a half-integer position `c`. At each step, we reflect it over an integer position note `n` by setting `c = 2*n-c`. If `n` is valid, `c` changes by ±1 mod 8. If `n` is invalid, `c` changes by ±3 mod 8. We cumulatively reduce over the input to collect all values of `c`, and then see if all notes were valid. We do this for every starting value of `c`, because it's shorter than checking just the ones adjacent to the first note.

Formatted:

```
f
  ! -
      aV J .u
              % -
                  y s Y
                  N
                8
              z
              T
         t J
      ,
        1
        7
  cR2 T

```

Test suite.
> 9 votes

# Answer
## CJam, ~~34~~ 31 bytes

```
8,q{~2*f{_@-_zF8b&,@@+8,=*}0-}/

```

Did this on my phone, so I'll have to put up an explanation later. Output is nonempty iff truthy.

Try it online | Test suite

### Explanation

The new code shifts the layout a little:

```
2    3    4

1    .    5

0/8  7    6

```

Even numbers correspond to string positions and odd numbers correspond to crank positions.

Here's what happens:

```
8,           Create the range [0 1 .. 7] of possible starting positions
             We can leave the string positions [0 2 4 6] in since it doesn't matter
q{ ... }/    For each character in the input...
  ~2*          Evaluate as integer and double, mapping "1234" -> [2 4 6 8]
  f{ ... }     Map over our possible current crank positions with the string
               position as an extra parameter
    _@-          Calculate (string - crank), giving some number in [-7 ... 7]
    _z           Duplicate and absolute value
    F8b          Push 15 base 8, or [1 7]
    &,           Setwise intersection and get length. If (string - crank) was in
                 [-7 -1 1 7] then the move was valid and this evaluates to 1, otherwise 0
    @@+          Calculate ((string - crank) + string)
    8,=          Take modulo 8, giving the new crank position. x%y in Java matches the
                 sign of x, so we need to do ,= (range + index) to get a number in [0 .. 7]
    *            Multiply the new crank position by our previous 0 or 1
  0-           Remove all 0s, which correspond to invalid positions

```

The stack is then automatically printed at the end. Any possible ending positions will be in the output, e.g. for the input `1` the output is `31`, which means the crank can end facing either left or up.

If only CJam had filter with extra parameter...

---

Edit: Temporarily rolling back while I convince myself that this 29-byte works:

```
8,q{~2*f{_@-_7b1#@@+8,=|}W-}/

```
> 17 votes

# Answer
## Haskell, ~~93 88~~ 87 bytes

```
any(all(\(a,b:c)->1>mod(a!!1-b)4).(zip=<<tail)).mapM((\a->[[a,a+1],[a+1,a]]).read.pure)

```

This evaluates to an anonymous function that takes a string and returns a boolean. Test suite here.

## Explanation

The idea is that the lambda on the right maps a number `a` to `[[a,a+1],[a+1,a]]`, the two possible "moves" that take the crank over that number, according to the following diagram:

```
  1 (2) 2

(1/5)  (3)

  4 (4) 3

```

In the main anonymous function, we first do `mapM((...).read.pure)`, which converts each character to an integer, applies the above lambda to it, and chooses one of the two moves, returning the list of all resulting move sequences. Then, we check if any of these sequences has the property that the second number of each move equals the first number of the next modulo 4, which means that it's a physically possible sequence. To do this, we `zip` each move sequence with its `tail`, check the condition for `all` the pairs, and see if `any` sequence evaluates to `True`.
> 7 votes

# Answer
# Retina, 50 bytes

```
A`13|31|24|42|(.)(?!\1)(.)(\2\2)*(\1|\2(?!\1|\2).)

```

I think this works?

Try it here.
> 7 votes

# Answer
## Retina, ~~127~~ 109 bytes

```
^((1|2)|(2|3)|(3|4)|(4|1))((?<2-5>1)|(?<5-2>1)|(?<3-2>2)|(?<2-3>2)|(?<4-3>3)|(?<3-4>3)|(?<5-4>4)|(?<4-5>4))*$

```

This prints `0` or `1`, accordingly.

Try it online! (This is a slightly modified version which marks all matches in the input instead of printing `0` or `1`.)

I tried coming up with an elegant algorithm, but my first few attempts weren't able to circumvent backtracking... and implementing backtracking is annoying... so I used a language which does the backtracking for me where I just need to encode a valid solution. Unfortunately, the encoding is fairly verbose and fairly redundant... I'm sure this can be shortened.

While I try to figure out something neater, if anyone wants to sort out how this works, here is a somewhat more readable version:

```
^
(
    (?<a>1|2)
  | (?<b>2|3)
  | (?<c>3|4)
  | (?<d>4|1)
)
(
    (?<a-d>1) | (?<d-a>1)
  | (?<b-a>2) | (?<a-b>2)
  | (?<c-b>3) | (?<b-c>3)
  | (?<d-c>4) | (?<c-d>4)
)*
$

```

And here is a hint:

```
1  a  2

d  O  b

4  c  3

```
> 6 votes

# Answer
# MATL, ~~57~~ 55 bytes

```
1t_hjnZ^!t1tL3$)2_/wvG1)UGnl2$Ov+Ys.5tv3X53$Y+4X\G!U=Aa

```

This uses current release (10.2.1), which is earlier than this challenge.

*EDIT (17 January, 2017): due to changes in the language, `v`* needs *to be replaced by `&v`, and `tL3$)` by `Y)` (in addition, some other improvements* could *be done). The following link includes those two modifications*

**Try it online!**

### Explanation

This is based on two of my favourite tools for code golf: *brute force* and *convolution*.

The code defines the *path* followed by the crank in terms of coordinates `0.5`, `1.5` etc. Each number tells the position of the crank between notes. The code first builds a *path array* with all possible paths that start with the first note of the input string. Each path is a column in this array. This is the *brute force* component.

From this path array, a *note array* is obtained, where each column is a realizable sequence of played notes. For example, movement from position `0.5` to `1.5` produces a note `1`. This consists in taking the average between positions and then applying a modulo 4 operation. The running average along each column is done with a 2D *convolution*.

Finally, the program checks if any column of the note array coincides with the input.

```
1t_h        % row array [1, -1]
j           % input string
nZ^!        % Cartesian power of [1, -1] raised to N, where "N" is length of string
t           % duplicate
1tL3$)      % extract first row
2_/         % divide by -2
wv          % attach that modified row to the top of Cartesian power array
G1)U        % first character of input string converted to number, "x"
Gnl2$O      % column array of N-1 zeros, where N is length of input
v           % concat vertically into column array [x;0;0...;0]
+           % add with singleton expansion
Ys          % cumulative sum along each column. Each column if this array is a path
.5tv        % column array [.5;.5]
3X5         % predefined string 'same' (for convolution)
3$Y+        % 2D convolution of path array with [.5;.5]
4X\         % modified modulo operation. This gives note array with values 1,2,3,4
G!U         % column array of input string characters converted to numbers
=Aa         % true if any column of the note array equals this

```
> 6 votes

# Answer
# Pyth, 43

```
Km-R2sMdc`M%R4-VJjQTtJ`0|Fm!s-VKdCm_B^_1dlK

```

Test Suite

This is probably very golfable, and also not the optimal algorithm for golfing (I expect enumerating all paths will be shorter?)... Anyway, if you find any error with the algorithm please let me know, I think it should work but I've been wrong before!

I'll explain my algorithm using the example input of `1221`. This program first maps the digits against their successors, like so: `[[1,2],[2,2],[2,1]]`. Then it gets their differences mod `4` (Pyth gets the result that matches the sign of the right argument of `%`, so this is always positive) : `[3,0,1]`. Then the results are split on `0` and have `2` subtracted from each of them: `[[1],[-1]]`.

Now that the setup is done, we create a list of `[-1,1,-1...]` and its negation `[1,-1,...]`, both the same length as the resulting array from before. Then, for each of these lists, perform setwise subtraction between the elements of the list and the list generated in the earlier step. Then, if either of the results contains only empty lists, we output true.
> 5 votes

# Answer
## ES6, ~~104~~ 100 bytes

```
s=>!/13|24|31|42|3[24]{2}1|4[13]{2}2|1[24]{2}3|2[13]{2}4|(.).\1/.test(s.replace(/(.)(\1\1)+/g,"$1"))

```

Edit: Saved 4 bytes thanks to @DigitalTrauma.

This is a complete rewrite as my previous approach was flawed.

I start by reducing all runs of digits to 1 or 2 depending on whether there was an odd or even number in the run. I then look for all the illegal combinations:

* `13|24|31|42` (opposite sides)
* `3[24]{2}1` as `3221` and `3441` are illegal
* similarly for `4xx2`, `1xx3` and `2xx4` where `x` is either of the missing digits
* `(.).\1` as things like `121` are illegal (`111` has been reduced to `1` earlier)

If there are no illegal pairs or "triples" then the whole string is legal (proof by induction is left as an exercise because it's late night here).

I tried to simplify `3[24]{2}1|1[24]{2}3` using a negative lookahead assertion but it turned out to be longer that way.
> 4 votes

# Answer
# Matlab, ~~279~~ 180 bytes

```
o=eye(4);a=input('')-'0';M=[o,o(:,[4,1:3]);o(:,[2:4,1:4,1])];x=2;for p=[a(1),mod(a(1),4)+1];for k=a;i=find(M*[o(:,k);o(:,p)]>1);if i;p=mod(i-1,4)+1;else;x=x-1;break;end;end;end;x>0

```

Quite a lazy solution, but the shortest I was able to come up with. I created special matrix: When you encode the state of the plucker and the last string that is to be plucked, it returns a vector, that encodes the new position of the plucker, and whether the previous *pluck* was possible at all. Now we just loop over all notes from the two possible start positions and see if one of them results in a playable melody. Can probably be golfed a lot more.

Expanded and explained source:

```
o=eye(4);
a=input('')-'0';

% encoding of plucker/notes
%      1
%   1     2
%4           2
%   4     3
%      3
%

M=[...
%12 3 4 1 2 3 4 <
1,0,0,0,0,1,0,0; %1  k = current note
0,1,0,0,0,0,1,0; %2
0,0,1,0,0,0,0,1; %3
0,0,0,1,1,0,0,0; %4
0,0,0,1,0,0,0,1; %1  p = current position of plucker
1,0,0,0,1,0,0,0; %2
0,1,0,0,0,1,0,0; %3
0,0,1,0,0,0,1,0];%4
% the vector we multiply with this matrix has following structure,
% the k-th and the p+4 th entries are 1, the rest 0
% when we multiply this vecotr with this matrix, we get a vector with an
% entry of value 2 IF this is a valid move ( mod(positionOfThe2 -1,4)+1 is
% the position of the plucker now)
% or only entries less than 2 it is impossible
x=2;  %number of "chances" to get it right
for p=[a(1),mod(a(1),4)+1] %check both starting values;
    for k=a;                %loop throu the notes
        size(M);

        c = M * [o(:,k);o(:,p)];
        i=find(c>1);               %did we find a 2?
        if i;
           p=mod(i-1,4)+1;         %if yes, valid move
        else;
            x=x-1;                 %if no, invalid,
            break;
        end
    end
end
x=x>0 %if we failed more than once, it is not possible

```
> 4 votes

# Answer
## Lua, ~~146 142 108 162 159 149 144 135 132 118~~ 113 bytes

```
z,q,s=0,0,io.read()for i in s:gmatch'.'do t=i-z if 2==math.abs(t)or t==q then return''end q=-t z=i end return 2>1

```

Returns true or false given a string of numbers between 1 and 4. (Doesn't handle no data or out of range numbers.

Simply tracks what the last movement was and checks if this movement is a reversal of the last movement (IE, 121 or 12221) or if the distance moving is more than possible.

**EDIT 1**:

Saved 6 bytes. I forgot that `if (int) then` returns true if int is non zero.

Thus:

```
if t~=0 then

```

changes to:

```
if t then

```

Also saved a few bytes by restructuring.

**EDIT 2**:

I'm slowly figuring this out. I've been reading the documentation here: http://www.lua.org/pil/ And one of the more useful pages there for golfing is http://www.lua.org/pil/3.3.html

In particular, this is very helpful:

> Like control structures, all logical operators consider false and nil as false and anything else as true.

What this means for me is that I can go ahead and remove my declaration for q (**which was initially set to 0**) as it will be regarded as "false" until it is set. So I save a few more bytes through this.

Another thing worth mentioning, though I don't use it, is if you want to swap values in Lua, you can simply do `a,b=b,a` without the need for a temporary variable.

**EDIT 3**

So, through some clever reconstruction as well as a new function, I've got the byte count down by 9 more.

**Best Mode for Receiving Input**

If you need to read in a list of numbers and do operations on them one at a time, you can use:

```
for x in string:gmatch('.') do
    print(x) --This is our number
end

```

When compared to your alternative using string:sub, you can see the value for golf (or general use):

```
for x=1,string:len() do
    print(string:sub(x,x)) --This is our number
end

```

**Restructure Functions or Strings**

Second thing, if you have multiple declarations on one line and one of the values is a function or you have a condition in which you compare a number to the result of a function like these:

```
x,y,z=io.read(),0,0 print('test')

if math.abs(x)==2 then

```

by restructuring it so the closing parenthesis are the last character in the condition or declaration, you can cut out a character like so:

```
y,z,x=0,0,io.read()print('test') --Notice no space

if 2==math.abs(x)then --If we put the '2' first in the conditional statement, we can now remove a space character

```

**Return Conditions that Equate to True or False instead of 'True' or 'False'**

I found a semi amusing way to cut my byte count down yet further. If you need to return true or false, you can return a statement that equates to true or false that has less characters than "true" or "false" themselves.

For instance, compare:

```
return true
return false

```

To:

```
return 2>1
return 1>2

```
> 2 votes

# Answer
# JavaScript (ES6), 80 bytes

```
s=>[r=0,1,2,3].map(i=>[...s].map(n=>n-1-i%4?n%4-i%4?v=0:i+=3:i++,v=1)|v?r=1:0)|r

```

## Explanation

`i%4` is the current crank position:

```
    1 (i%4 == 1) 2

(i%4 == 0) (i%4 == 2)

    4 (i%4 == 3) 3

```

### Indented and Commented

```
s=>
  [r=0,1,2,3].map(i=> // i = crank position, test for i starting at 0 to 3, r = result
    [...s].map(n=>    // for each note n
      n-1-i%4?        // if n is not at the position after i
        n%4-i%4?      // if n is not at the position before i
          v=0         // set the result of this test to invalid
        :i+=3         // else i-- (+3 used because i%4 would break for negative values)
      :i++,           // else i++
      v=1             // v = result of test, initialise to 1 (valid)
    )
    |v?r=1:0          // if the test returned true, set the result to true
  )
  |r                  // return the result

```

## Test

```
var solution = s=>[r=0,1,2,3].map(i=>[...s].map(n=>n-1-i%4?n%4-i%4?v=0:i+=3:i++,v=1)|v?r=1:0)|r
```

```
<input type="text" value="1221441" oninput="result.textContent=solution(this.value)" />
<pre id="result"></pre>
```
> 2 votes

# Answer
## Python (3.5) ~~160~~ ~~151~~ 150 bytes

A recursive solution

```
def f(s):g=lambda s,c:s==''or g(s[1:],(c[:4]*2)[(s[0]==c[0])*2+1:])if s==''or s[0]in c[:2]else 0;return any([g(s,"1234123"[i:])for i in range(4)])

```

## Ungolfed without lambda

```
def f(s):
    def g(s,c):
        if s=='' or s[0] in c[:2] :
            return s=='' or g(s[1:],(c[:4]*2)[(s[0]==c[0])*2+1:])
        else:
            return False
    return any([g(s,"1234123"[i:]) for i in range(4)])

```

I rotate all the box instead of the crank. The crank position is between first and second character of the c string. I need to test all beginning position of the crank.

**Trick use to rotate the string**

The usual way to rotate a string in python (`s[i:]+s[:i]`) need too repeat both index and string. In this case i duplicate the string and crop first characters.

```
(c*2)                        # duplicate the string
     [(s[0]==c[0])*2+1       # test that return 1 if firsts characters match 3 instead
                      :]
                        [:4] # crop again to have a 4 characters string

```

## Test cases

```
[f(i) for i in ["1", "1234", "1221", "3333", "143332", "22234", "2234", "22214", "1221441", "41233", "13", "1224", "121", "12221", "43221"]]
[True, True, True, True, True, True, True, True, True, True, False, False, False, False, False]

```
> 2 votes

# Answer
# MATL, 49 bytes (non-competing1)

1. The answer (ab)uses the less strict indexing of newer versions of MATL, and would not have worked at the time this challenge was posted.

```
dt~aX`tt~f1)q:)w3MQJh)_ht~a]tT-3hX|n2=wT_3hX|n2=+

```

Try it online!.

I saw this challenge at the Best of PPCG 2016, and figured that this could use my favourite operator:

```
d

```

Or, `diff` in MATLAB/Octave (I will freely use MATLAB/Octave terminology in my explanation, since it is easier to read for humans). This command calculates the element-wise difference in a vector or, in this case, in a character array.

For this problem, the differences exhibit an interesting pattern. Note that

> An change in direction **must** mean that a note is played **twice**.

For the difference pattern (ignoring the `1-4` transition for now), this means that

> A change in sign in `diff(input)` must have an **odd** number of zeroes in between. Conversely, the sign is not allowed to change after an **even** number of zeroes.

---

I implemented this by, for each array, finding the first zero. I trim the zero out, and multiply all elements after it by `-1`. For the end result, this means that all elements **must** have the same sign. Of course, there is the small issue of the `-3` equalling `+1`, and `2` being disallowed in general. I solved this by taking the set union of the result with `[1 -3]`, and checking whether this is of size 2 (i.e., no disallowed elements 'entered' the set through the union). Repeat for `[-1 3]`, and check whether either (or both, in the case of a 1-length input) is true.

```
d                                % Difference of input
 t~a                             % Check if any element equals 0
    X`                     t~a]  % Start while loop, ending in the same check
       t~                           % Get a new vector, logical negated to find zeroes.
          f1)                       % Find the position of the first zero.
      t         q:)                 % Decrement by 1, to index all elements before that zero.
                   w3MQJh)          % Push the result of 'find', but increment to get all elements after.
                         _h         % Multiply the second half by -1, and concatenate horizontally.

  T-3hX|n2=                      % Check if set union with [1 -3] is size 2
 t        wT_3hX|n2=             % Check if set union with [-1 3] is size 2
                    +            % Logical OR.

```
> 2 votes

# Answer
# Python 2, 65 bytes

```
n=15
for c in input():k=2**int(c);n=n*17/k%4*5/2%4*k%15
print n>0

```

Try it online!
> 2 votes

# Answer
# JavaScript (ES2015), ~~110~~ 95

```
p=(s,d)=>(h=s[0],t=s.slice(1),g=t[0],!g||(d?g==h?p(t,-d):g%4==(h-d)%4&&p(t,d):p(s,1)||p(s,-1)))

```

15 bytes saved by Neil! Original version ungolfed:

```
p = (s, d) => {
  h = s[0]
  t = s.substr(1)

  if (!t[0]) return true
  if (!d) return p(s, 1) || p(s, -1)
  if (t[0] == h) return p(t, d*-1)
  if (t[0] == (h-d > 4 ? 1 : h-d || 4)) return p(t, d)

  return false
}

```

Tests: https://jsbin.com/cuqicajuko/1/edit?js,console
> 1 votes

# Answer
# Turing machine code, 395 bytes

```
0 1 _ r a
0 2 _ r b
0 3 _ r c
0 4 _ r d
a 1 _ r a
a 2 _ r E
a 3 _ r h
a 4 _ r S
b 1 _ r W
b 2 _ r b
b 3 _ r S
b 4 _ r h
c 1 _ r h
c 2 _ r N
c 3 _ r c
c 4 _ r W
d 1 _ r N
d 2 _ r h
d 3 _ r E
d 4 _ r d
N 1 _ r W
N 2 _ r E
N _ _ r r
N * _ r h
E 2 _ r N
E 3 _ r S
E _ _ r r
E * _ r h
S 3 _ r E
S 4 _ r W
S _ _ r r
S * _ r h
W 4 _ r S
W 1 _ r N
W _ _ r r
W * _ r h
h _ 0 r halt
h * _ r h
r _ 1 r halt

```

Try it online!

This is basically a state-based approach:

* The initial state is 0.
* `a`, `b`, `c`, and `d` are "undecided states" that only occur at the beginning
* `N`, `E`, `S`, and `W` are the "decided states", obviously standing for `N`orth, `E`ast, `S`outh, and `W`est.
> 1 votes

# Answer
# Thue, 203 bytes

I can't think of how to golf this farther.

```
0::=:::
>11::=>1
>22::=>2
>33::=>3
>44::=>4
>12::=b
>21::=d
>14::=c
>41::=a
>23::=c
>32::=a
>34::=d
>43::=b
a1::=d
a2::=b
b2::=a
b3::=c
c3::=b
c4::=d
d4::=c
d1::=a
a<::=~n
b<::=~e
c<::=~s
d<::=~w
::=
>0<

```

If the note sequence is possible, will output ending direction, otherwise the output will be empty.
> 1 votes

# Answer
# Prolog (SWI), 117 bytes

```
a(N,P):-P=N;N=1,P=4,!;P is N-1.
m([A,B|C],[X,Y|Z]):-a(A,X),a(B,X),a(B,Y),X\=Y,m([B|C],[Y|Z]).
m([_],_).
p(N):-m(N,_).

```

Defines a predicate `p` that succeeds on playable inputs (given as a list of integers) and fails on unplayable ones. Try it online!

### Explanation

`a` defines an adjacency relation between note `N` and crank position `P`. We define position *p* to be between notes *p* and *p+1*. Thus, a position is adjacent to note `N` iff

* it equals `N` (`P=N`); **or**
* the note is 1 and the position is 4 (`N=1,P=4`); **or**
* the above case is not true (`!`) and the position equals `N-1` (`P is N-1`).

`m` takes a list of notes and tries to generate a list of positions that will play those notes. `A` is the note just played, `B` is the note about to be played; `X` is the current crank position, `Y` is the next crank position. A move is valid iff

* the note just played is adjacent to the current crank position (`a(A,X)`);
* the note about to be played is also adjacent to the current crank position (`a(B,X)`);
* the note about to be played is adjacent to the next crank position (`a(B,Y)`); and
* the two crank positions are not equal (`X\=Y`).

If all of these hold, recurse. If we successfully get down to any one note (`m([_],_)`), the sequence of notes is playable.

For this question, we only care whether a sequence of moves exists, so we define `p` to call `m` and discard the generated list of crank positions.

See an ungolfed version and verify all test cases here.
> 1 votes

---
Tags: code-golf, decision-problem, graph-theory
---


# Question
Title: Historical difference between `/` and `÷` in mathematical expressions
## Introduction:

> Inspired by a discussion that is already going on for many years regarding the expression \\$6÷2(1+2)\\$.
>
> With the expression \\$6÷2(1+2)\\$, mathematicians will quickly see that the correct answer is \\$1\\$, whereas people with a simple math background from school will quickly see that the correct answer is \\$9\\$. So where does this controversy and therefore different answers come from? There are two conflicting rules in how \\$6÷2(1+2)\\$ is written. One due to the part `2(`, and one due to the division symbol `÷`.
>
> Although both mathematicians and 'ordinary people' will use *PEMDAS* (Parenthesis - Exponents - Division/Multiplication - Addition/Subtraction), for mathematicians the expression is evaluated like this below, because \\$2(3)\\$ is just like for example \\$2x^2\\$ a monomial a.k.a. "*a single term due to implied multiplication by juxtaposition*" (and therefore part of the `P` in `PEMDAS`), which will be evaluated differently than \\$2×(3)\\$ (a binomial a.k.a. two terms):
>
> $$6÷2(1+2) → \frac{6}{2(3)} → \frac{6}{6} → 1$$
>
> Whereas for 'ordinary people', \\$2(3)\\$ and \\$2×(3)\\$ will be the same (and therefore part of the `MD` in `PEMDAS`), so they'll use this instead:
>
> $$6÷2(1+2) → 6/2×(1+2) → 6/2×3 → 3×3 → 9$$

However, even if we would have written the original expression as \\$6÷2×(1+2)\\$, there can still be some controversy due to the use of the division symbol `÷`. In modern mathematics, the `/` and `÷` symbols have the exact same meaning: divide. Some rules pre-1918 regarding the division symbol `÷`*††* state that it had a different meaning than the division symbol `/`. This is because `÷` used to mean "*divide the number/expression on the left with the number/expression on the right*"*†††*. So \\$a ÷ b\\$ then, would be \\$(a) / (b)\\$ or \\$\frac{a}{b}\\$ now. In which case \\$6÷2×(1+2)\\$ would be evaluated like this by people pre-1918:

$$6÷2×(1+2) → \frac{6}{2×(1+2)} → \frac{6}{2×3} → \frac{6}{6} → 1$$

*†: Although I have found multiple sources explaining how `÷` was used in the past (see ††† below), I haven't been able to find definitive prove this changed somewhere around 1918. But for the sake of this challenge we assume 1918 was the turning point where `÷` and `/` starting to mean the same thing, where they differed in the past.*

> *††: Other symbols have also been used in the past for division, like `:` in 1633 (or now still in The Netherlands and other European non-English speaking countries, since this is what I've personally learned in primary school xD) or `)` in the 1540s. But for this challenge we only focus on the pre-1918 meaning of the obelus symbol `÷`.*
> *†††: Sources: this article in general. And the pre-1918 rules regarding `÷` are mentioned in: this*The American Mathematical Monthly *article from February 1917**; this German* Teutsche Algebra *book from 1659 page 9 and page 76; this*A First Book in Algebra *from 1895 page 46 \[48/189\]**.*
>
> Slightly off-topic: regarding the actual discussion about this expression: **It should never be written like this in the first place!** The correct answer is irrelevant, if the question is unclear. *\*Clicks the "close because it's unclear what you're asking" button\**.
> And for the record, even different versions of Casio calculators don't know how to properly deal with this expression:

## Challenge:

You are given two inputs:

* A (valid) mathematical expression consisting only of the symbols `0123456789+-×/÷()`
* A year

And you output the result of the mathematical expression, based on the year (where `÷` is used differently when \\$year\<1918\\$, but is used exactly the same as `/` when \\$year\ge1918\\$).

## Challenge rules:

* You can assume the mathematical expression is valid and only uses the symbols `0123456789+-×/÷()`. This also means you won't have to deal with exponentiation. (You are also allowed to use a different symbols for `×` or `÷` (i.e. `*` or `%`), if it helps the golfing or if your language only supports ASCII.)
* You are allowed to add space-delimiters to the input-expression if this helps the (perhaps manual) evaluation of the expression.
* I/O is flexible. Input can be as a string, character-array, etc. Year can be as an integer, date-object, string, etc. Output will be a decimal number.
* You can assume there won't be any division by 0 test cases.
* You can assume the numbers in the input-expression will be non-negative (so you won't have to deal with differentiating the `-` as negative symbol vs `-` as subtraction symbol). The output can however still be negative!
* You can assume `N(` will always be written as `N×(` instead. We'll only focus on the second controversy of the division symbols `/` vs `÷` in this challenge.
* Decimal output-values should have a precision of at least three decimal digits.
* If the input-expression contains multiple `÷` (i.e. \\$4÷2÷2\\$) with \\$year\<1918\\$, they are evaluated like this: \\$4÷2÷2 → \frac{4}{\frac{2}{2}} → \frac{4}{1} → 4\\$. (Or in words: *number \\$4\\$ is divided by expression \\$2 ÷2\\$, where expression \\$2 ÷2\\$ in turn means number \\$2\\$ is divided by number \\$2\\$*.)
* Note that the way `÷` works implicitly means it has operator precedence over `×` and `/` (see test case \\$4÷2×2÷3\\$).
* You can assume the input-year is within the range \\$\[0000, 9999\]\\$.

## 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 with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Input-expression:   Input-year:   Output:      Expression interpretation with parenthesis:

6÷2×(1+2)           2018          9            (6/2)×(1+2)
6÷2×(1+2)           1917          1            6/(2×(1+2))
9+6÷3-3+15/3        2000          13           ((9+(6/3))-3)+(15/3)
9+6÷3-3+15/3        1800          3            (9+6)/((3-3)+(15/3))
4÷2÷2               1918          1            (4/2)/2
4÷2÷2               1900          4            4/(2/2)
(1÷6-3)×5÷2/2       2400          -3.541...    ((((1/6)-3)×5)/2)/2
(1÷6-3)×5÷2/2       1400          1.666...     ((1/(6-3))×5)/(2/2)
1×2÷5×5-15          2015          -13          (((1×2)/5)×5)-15
1×2÷5×5-15          1719          0.2          (1×2)/((5×5)-15)
10/2+3×7            1991          26           (10/2)+(3×7)
10/2+3×7            1911          26           (10/2)+(3×7)
10÷2+3×7            1991          26           (10/2)+(3×7)
10÷2+3×7            1911          0.434...     10/(2+(3×7))
4÷2+2÷2             2000          3            (4/2)+(2/2)
4÷2+2÷2             1900          2            4/((2+2)/2)
4÷2×2÷3             9999          1.333...     ((4/2)×2)/3
4÷2×2÷3             0000          3            4/((2×2)/3)
((10÷2)÷2)+3÷7      2000          2.928...     ((10/2)/2)+(3/7)
((10÷2)÷2)+3÷7      1900          0.785...     (((10/2)/2)+3)/7
(10÷(2÷2))+3×7+(10÷(2÷2))+3×7
                    1920          62           (10/(2/2))+(3×7)+(10/(2/2))+(3×7)
(10÷(2÷2))+3×7+(10÷(2÷2))+3×7
                    1750          62           (10/(2/2))+(3×7)+(10/(2/2))+(3×7)
10÷2/2+4            2000          6.5          ((10/2)/2)+4
10÷2/2+4            0100          2            10/((2/2)+4)
9+6÷3-3+15/3        9630          13           9+(6/3)-3+(15/3)
9+6÷3-3+15/3        0369          3            (9+6)/(3-3+(15/3))

```

# Answer
# , ~~68~~ 66 bytes

```
function(x,y,`=`=`/`)eval(parse(t=`if`(y<1918,x,gsub('=','/',x))))

```

Try it online!

Expects equality sign `=` instead of `÷` and `*` instead of `×`.

The code makes use of some nasty operator overloading, making advantage of the fact that `=` is a right-to-left operator with very low precedence (the exact behavior that we want from pre-1918 `÷`), and R retains its original precedence when it is overloaded. The rest is automatically done for us by `eval`.

As a bonus, here is the same exact approach implemented in terser syntax. This time our special division operator is tilde (`~`):

# Julia 0.7, 51 bytes

```
~=/;f(x,y)=eval(parse(y<1918?x:replace(x,'~','/')))

```

Try it online!
> 26 votes

# Answer
# JavaScript (ES6),  ~~130 129~~  120 bytes

*Saved 9 bytes thanks to @ScottHamper*

Takes input as `(year)(expr)`. Expects `%` and `*` instead of `÷` and `×`.

```
y=>g=e=>(e!=(e=e.replace(/\([^()]*\)/,h=e=>eval(e.split`%`.reduceRight((a,c)=>y<1918?`(${c})/(${a})`:c+'/'+a))))?g:h)(e)

```

Try it online!

## How?

### Processing leaf expressions

The helper function \\$h\\$ expects a leaf expression \\$e\\$ as input, processes all `%` symbols according to the rules of the year \\$y\\$ (defined in the parent scope) and evaluates the resulting string.

If \\$y\<1918\\$, we transform `X%Y` into `(X)/(Y)`, to enforce low precedence and repeat this process for the entire string from right to left to enforce right-to-left associativity.

Examples:

* `8%2` becomes `(8)/(2)`, whose simplified form is `8/2`
* `2+3%3+2` becomes `(2+3)/(3+2)`
* `8%2%2` becomes `(8)/((2)/(2))`, whose simplified form is `8/(2/2)`

If \\$y\ge 1918\\$, each `%` is simply turned into a `/`.

```
h = e =>                    // e = input string
  eval(                     // evaluate as JS code:
    e.split`%`              //   split e on '%'
    .reduceRight((a, c) =>  //   for each element 'c', starting from the right and
                            //   using 'a' as the accumulator:
      y < 1918 ?            //     if y is less than 1918:
        `(${c})/(${a})`     //       transform 'X%Y' into '(X)/(Y)'
      :                     //     else:
        c + '/' + a         //       just replace '%' with '/'
    )                       //   end of reduceRight()
  )                         // end of eval()

```

### Dealing with nested expressions

As mentioned above, the function \\$h\\$ is designed to operate on a leaf expression, i.e. an expression without any other sub-expression enclosed in parentheses.

That's why we use the helper function \\$g\\$ to recursively identify and process such leaf expressions.

```
g = e => (            // e = input
  e !=                // compare the current expression with
    ( e = e.replace(  // the updated expression where:
        /\([^()]*\)/, //   each leaf expression '(A)'
        h             //   is processed with h
      )               // end of replace()
    ) ?               // if the new expression is different from the original one:
      g               //   do a recursive call to g
    :                 // else:
      h               //   invoke h on the final string
)(e)                  // invoke either g(e) or h(e)

```
> 6 votes

# Answer
# Python 3.8 (pre-release), ~~324~~ ~~310~~ 306 bytes

```
lambda s,y:eval((g(s*(y<1918))or s).replace('%','/'))
def g(s):
 if'%'not in s:return s
 l=r=j=J=i=s.find('%');x=y=0
 while j>-1and(x:=x+~-')('.find(s[j])%3-1)>-1:l=[l,j][x<1];j-=1
 while s[J:]and(y:=y+~-'()'.find(s[J])%3-1)>-1:r=[r,J+1][y<1];J+=1
 return g(s[:l]+'('+g(s[l:i])+')/('+g(s[i+1:r])+')'+s[r:])

```

Try it online!

Takes `%` instead of `÷` and `*` instead of `×`
> 5 votes

# Answer
# Perl 5, ~~47~~ ~~97~~ 95 bytes

~~```
/ /;$_="($`)";$'<1918?s-%-)/(-g:y-%-/-;$_=eval

```~~
```
$_="($F[0])";1while$F[1]<1918&&s-\([^()]+\)-local$_=$&;s,%,)/((,rg.")"x y,%,,-ee;y-%-/-;$_=eval

```

TIO
> 2 votes

# Answer
# Rust - ~~1066~~ ~~860~~ ~~783~~ ~~755~~ 740 bytes

```
macro_rules! p{($x:expr)=>{$x.pop().unwrap()}}fn t(s:&str,n:i64)->f64{let (mut m,mut o)=(vec![],vec![]);let l=|v:&Vec<char>|*v.last().unwrap();let z=|s:&str|s.chars().nth(0).unwrap();let u=|c:char|->(i64,fn(f64,f64)->f64){match c{'÷'=>(if n<1918{-1}else{6},|x,y|y/x),'×'|'*'=>(4,|x,y|y*x),'-'=>(2,|x,y|y-x),'+'=>(2,|x,y|y+x),'/'=>(5,|x,y|y/x),_=>(0,|_,_|0.),}};macro_rules! c{($o:expr,$m:expr)=>{let x=(u(p!($o)).1)(p!($m),p!($m));$m.push(x);};};for k in s.split(" "){match z(k){'0'..='9'=>m.push(k.parse::<i64>().unwrap() as f64),'('=>o.push('('),')'=>{while l(&o)!='('{c!(o,m);}p!(o);}_=>{let j=u(z(k));while o.len()>0&&(u(l(&o)).0.abs()>=j.0.abs()){if j.0<0&&u(l(&o)).0<0{break;};c!(o,m);}o.push(z(k));}}}while o.len()>0{c!(o,m);}p!(m)}

```

Rust does not have anything like 'eval' so this is a bit tough. Basically, this is a bog-standard Djisktra shunting-yard infix evaluator with a minor modification. ÷ is an operator with a variable precedence: lower than everything else (but parenthesis) in \<1918 mode, higher than everything else in \>=1918 mode. It is also 'right associated' (or left?) for \<1918 to meet the 4÷2÷2 specification, and association is 'faked' by making ÷ precedence negative, then during evaluation treating any precedence \<0 as associated. There's more room for golfing but this is a good draft i think.

Ungolfed at play.rust-lang.org
> 1 votes

---
Tags: code-golf, math, number, arithmetic, integer
---


title: Countries by Area

text:
# Question
Title: Countries by Area
# Challenge

Given two non negative integers `a < b`, output all countries, from the below Top 100 Countries, where area is between `a` and `b`: `a<= area <= b`.

# Example

```
147500,180000   --> uruguay, suriname, tunisia, bangladesh
1200000,1300000 --> peru, chad, niger, angola, mali, south africa
1234567,1256789 --> angola, mali

```

# Top 100 Countries by Area (2017):

```
russia..........................17098250
canada...........................9984670
united states....................9831510
china............................9562911
brazil...........................8515770
australia........................7741220
india............................3287259
argentina........................2780400
kazakhstan.......................2724902
congo............................2686860
algeria..........................2381740
saudi arabia.....................2149690
mexico...........................1964380
indonesia........................1910931
sudan............................1879358
libya............................1759540
iran.............................1745150
mongolia.........................1564120
peru.............................1285220
chad.............................1284000
niger............................1267000
angola...........................1246700
mali.............................1240190
south africa.....................1219090
colombia.........................1141749
ethiopia.........................1104300
bolivia..........................1098580
mauritania.......................1030700
egypt............................1001450
tanzania..........................947300
nigeria...........................923770
venezuela.........................912050
namibia...........................824290
mozambique........................799380
pakistan..........................796100
turkey............................785350
chile.............................756096
zambia............................752610
myanmar...........................676590
afghanistan.......................652860
south sudan.......................644330
somalia...........................637660
central african republic..........622980
ukraine...........................603550
madagascar........................587295
botswana..........................581730
kenya.............................580370
france............................549087
yemen.............................527970
thailand..........................513120
spain.............................505940
turkmenistan......................488100
cameroon..........................475440
papua new guinea..................462840
sweden............................447420
uzbekistan........................447400
morocco...........................446550
iraq..............................435050
greenland.........................410450
paraguay..........................406752
zimbabwe..........................390760
norway............................385178
japan.............................377962
germany...........................357380
finland...........................338420
vietnam...........................330967
malaysia..........................330800
cote d'ivoire.....................322460
poland............................312680
oman..............................309500
italy.............................301340
philippines.......................300000
burkina faso......................274220
new zealand.......................267710
gabon.............................267670
ecuador...........................256370
guinea............................245860
united kingdom....................243610
uganda............................241550
ghana.............................238540
romania...........................238390
laos..............................236800
guyana............................214970
belarus...........................207600
kyrgyz............................199949
senegal...........................196710
syria.............................185180
cambodia..........................181040
uruguay...........................176220
suriname..........................163820
tunisia...........................163610
bangladesh........................147630
nepal.............................147180
tajikistan........................141376
greece............................131960
nicaragua.........................130370
north korea.......................120540
malawi............................118480
eritrea...........................117600
benin.............................114760

```

## Names as separate list

```
russia
canada
united states
china
brazil
australia
india
argentina
kazakhstan
congo
algeria
saudi arabia
mexico
indonesia
sudan
libya
iran
mongolia
peru
chad
niger
angola
mali
south africa
colombia
ethiopia
bolivia
mauritania
egypt
tanzania
nigeria
venezuela
namibia
mozambique
pakistan
turkey
chile
zambia
myanmar
afghanistan
south sudan
somalia
central african republic
ukraine
madagascar
botswana
kenya
france
yemen
thailand
spain
turkmenistan
cameroon
papua new guinea
sweden
uzbekistan
morocco
iraq
greenland
paraguay
zimbabwe
norway
japan
germany
finland
vietnam
malaysia
cote d'ivoire
poland
oman
italy
philippines
burkina faso
new zealand
gabon
ecuador
guinea
united kingdom
uganda
ghana
romania
laos
guyana
belarus
kyrgyz
senegal
syria
cambodia
uruguay
suriname
tunisia
bangladesh
nepal
tajikistan
greece
nicaragua
north korea
malawi
eritrea
benin

```

## Areas as separate lists

```
17098250
9984670
9831510
9562911
8515770
7741220
3287259
2780400
2724902
2686860
2381740
2149690
1964380
1910931
1879358
1759540
1745150
1564120
1285220
1284000
1267000
1246700
1240190
1219090
1141749
1104300
1098580
1030700
1001450
947300
923770
912050
824290
799380
796100
785350
756096
752610
676590
652860
644330
637660
622980
603550
587295
581730
580370
549087
527970
513120
505940
488100
475440
462840
447420
447400
446550
435050
410450
406752
390760
385178
377962
357380
338420
330967
330800
322460
312680
309500
301340
300000
274220
267710
267670
256370
245860
243610
241550
238540
238390
236800
214970
207600
199949
196710
185180
181040
176220
163820
163610
147630
147180
141376
131960
130370
120540
118480
117600
114760

```

## Rules

* The input and output can be given in any convenient format.
* The output can be in any case.
* No need to handle invalid input values.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an on-line testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* The code is not allowed to import the list from file or internet.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# Node.js,  ~~1170~~  1164 bytes

Takes input as `(a)(b)`.

```
a=>b=>eval(require('zlib').inflateSync(Buffer.from('eNpFU8uS6jYQ/RVWyUzdU7cwmNeC2d9vSKUybattC9uSkeQh5utzZCbJBij147yaz0qdddBgU1DBKIM8LJwPqdv0Pj85W0uQdha0QbVWJLnZ3sYkDk4nGVCJawcxGjuk2dloBXEO1smomMPM0QW1jJU3ubKE/KlOW472S2iXJyodJMwR7byIEwziI4IfxbG17fLT3Ioz/HI2qdn01rXGj+y3jhS1nsX4gFYqn0k9Nk+lEGdQzYG9smkkekydHew0cSTCJhkWZAhMfm2tfdKN+d1+eRt0NWLJSr6sJipBY93a1mrg0IKbTNkAHx5U97RjJdVDMb2sWlavXgM2yB2jD76uPeZnpd/exYcaJbpMs2wy528xdEqDp45E7iPTeXVPwphSJ3ZduigraII4BtKrWwSVT/GRrRrFSCuRqWHuA8cUtboUZNhIE5im2wSd5mqwNSIdGHIefmbgcTaEkiZb/oIdmcfIRU/Gx7aaDupKTBcy/1Yy+rV8nxV0yubGL+b7nJkqz4eO8YWNzzVPbZcpkSQvJK0PlR/sVy6kzvopo/jBr3AvVi/SORELXpr/dynZiMGkYSaD/M4Jmu0w2GrJJ5jFWGc882Zp1L8tE4gyG7thTBlAhhe5Os+jl6f03SpJQkvLeDl5QW6cYzYwsw3ytEN2wv13jhxJvCk6S+vBQybe5884DTZ94vNnY4ek4e3tL+j79ePN/LgWxx+8lKi/XHr7LE/qsS9LysXuXBK7RMG/Tt51rCNU0Y0ljgozehykRNkxUsehzuCsDc6HEv70mioV+8tr0Y6T1c2jblnGiQui9Si0xKVgV0OISXE5KQ4FzqeAgc/j1OK83eJ4aAnbotyNCBfiETt4lOj2JJIUyuabL3Ei7ZZIzlQoyvFEAI9jmWCLC4auRHsmeOVxMR53Uey8IfrUo9ippZ/UQVqBRPfZCbMtcd9TwZZSiqxh19SUT91F1TnsptDA1S9BI6XZOyusyoU/jgNHm0SPzL5GcSgCilTtcZzuinPn6ciFAEV9arErbjXzLR0OGv2E2He05+z0gEus+dqXHmdnov8/zD/0T+y37+8fV/mt+rgamOv2/R9Hndmv','base64'))+'')

```

Try it online!

### Inflated code

```
`benin,eritrea,malawi,(…),russia`.split`,`
filter((_, e) =>
  (
    d += 16 + parseInt(
      `47eo,344,so,(…),8ndso`.split`,`[e],
      30
    )
  ) >= a & b >= d,
  d = 0
)

```

The base (30) and the hardcoded offset (16) were chosen to optimize the compression of the delta values.
> 4 votes

# Answer
# Wolfram Language 68 bytes

I am uncertain whether this satisfies the requirements.

This uses a built-in function named `CountryData`. Wolfram Language knows the areas of all the countries in the world, so it's simply a matter of determining those countries in which the area falls within the given interval.

```
 c=CountryData;Cases[c@"Countries",x_/;(a=c[x,"Area"][[1]])<=#2&&a>=#]&

```
> 4 votes

# Answer
# Python 3, ~~1961 1579~~ 1353 bytes

```
lambda a,b:["india,argentina,kazakhstan,congo,algeria,saudi arabia,mexico,indonesia,sudan,libya,iran,mongolia,peru,chad,niger,angola,mali,south africa,colombia,ethiopia,bolivia,mauritania,egypt,tanzania,nigeria,venezuela,namibia,mozambique,pakistan,turkey,chile,zambia,myanmar,afghanistan,south sudan,somalia,central african republic,ukraine,madagascar,botswana,kenya,france,yemen,thailand,spain,turkmenistan,cameroon,papua new guinea,sweden,uzbekistan,morocco,iraq,greenland,paraguay,zimbabwe,norway,japan,germany,finland,vietnam,malaysia,cote d'ivoire,poland,oman,italy,philippines,burkina faso,new zealand,gabon,ecuador,guinea,united kingdom,uganda,ghana,romania,laos,guyana,belarus,kyrgyz,senegal,syria,cambodia,uruguay,suriname,tunisia,bangladesh,nepal,tajikistan,greece,nicaragua,north korea,malawi,eritrea,benin,russia,canada,united states,china,brazil,australia".split(",")[i]for i in range(100)if a<=int((11*'1'+83*'0'+'a55554ynmlfa64411xrrrqqqonnmlkjjhhhgggeddddccccbbaaaa9999988888777766666'+10*'5'+'4444333333332222226yuo2lglel123yapeiji5pk4goj3gasjo42t74iztocxlgfrbzug6xllkbspd93n933wpmgfvqqh976432lga7yvrii551tsljigh0qyixgdj7rpqh4okvoqmyxnz3oaqxsq0t9zep2r60pp5vtodxdmu487kopui7mr4d8t9tihlkjtpyd2xpv6asvoze8wk3tl0fqj371st5rcq0gm4fe4eskogkqm904k2waqy0waou602s0ar6efucwcoocs6qeogey8kjw8k8kc8eaegyq4yseo56ww0kquc4kec4oseyif6w')[i::100],36)<=b]

```

Try it online!

*-382 bytes thanks to Shaggy*

*-226 bytes by a new data storage method and some changes by Jonathan Allan*
> 2 votes

# Answer
# 05AB1E, ~~845~~ ~~726~~ 724 bytes

```
Ÿ•LˆB1?+β»,¦ïp,fpîÃUK„»L`l¢~Rζ₃f(–α9OÌHíÜ$;’*Ê¸šöÏG∞zW¦pƒ;₃øÅ^êà©Q₁¤
cΘ¥₄₃₁¾«ål5ó eù&AŠ×Y‡p3ΓòÔ¬Š|üÛT∊DìaM1Gæ³RùVòí¢ʒʒP,vζšƶ«Ƶ¹”jWL¦¹†Ãн‘ƶËθ±…KãÐΓ¼¿λÎ‹½ª%=KHÛá$çöα=ÍTćÒ¹∞ïkÑ§qγHšÎGêĆ[‹Î½žMcǝEØιœ₆Î»Ô#ζ₆Σγ’Ƶä"‚žlóƒβÀÙlƵ=αн#$½/Y€Š:¹!
ÿFw91?ì3-ŸWuµ\ú‹µú1vPε»ã#º{ǝ¯¼¢vN=тLʒ”T³é¶ùÅγ¬ë‘/ÐžaÕÄ"Õ-Ý–°ǝ-β₆›*ŽBÂ₂₄q••17ò÷•вå.•1d|WÈ!ÝWàÁвZr¦h…ù„D&«r4¡8!’}`U²†ánB;ÂMÒ¤wt\pm≠¤Ëм h6oìIdšÁô1•#„af…a f:„di" d'i":`’ž¦0…¥0ƒŠ ƒ¼0‡¤0£‰0ˆ‚0Š™0²Ð0Û½0Ê›0Þ²0»´ Â¸0Žè0°×0Ïï0ÿ0¨¤0ãì0¾ç0Êä0èå0àÜ0çÐ0ƒÞ ‹…0Â©0×ˆ0ÎÝ0ÿ0¬æ0Ì¹0Äë0Ã£0ÌÚ0Øµ0¬¬0¤•0¸Ž0Ó±0ÜÞ0¹ä0ƒÞ Ïï0ê¢0‡Þ ïŽ •€0·±0Ý£0Êž0¼¤0ˆÖ0àç0§á0•ì0ÿ0å£0âŽ €¢ «á0§…0Ý©0ÊŒ0•°0ˆ¨ˆÑ0ßÚ0ÄÒ0¬ì0Šè0‰Í0²á0°‚0°ˆ0ÿ0¯¬0ß»0í¿0°¦0ÿ0€¢ ™Æ0ÿ0Ìè0«á0ƒŠ Šß0ÑÝ0Ó•0À‹0ìÞ0äß0Öæ0ÿ0ã¼0Ñè0ÍÆ0Õ·0ÿ0Úˆ0Éã0ÄÑ0ÿ0«š0ÚÊ0„¡ ¡è0à›0ÿ0ÿ’0¡sÏ

```

No smart golfs yet, but will see what I can do later on.

Try it online or verify all test cases.

**Explanation:**

```
Ÿ                    # Get the inclusive range of the two (implicit) inputs
 •...•               # Compressed integer 1973189551155729951158047504888550693285038979215196451111846739112857422275219605859797606876792240255951887197422137126381236888252746087204379433177795015673735312875287174369802127043070332938030374559331221793543099653787758410730754595832945510288634919093697357543931716347226050469833259385438225825153429642271254788538576531893907231375001829235576168553954340620130825485946678723358989342130504637082203898949974502648169087327686854812063938661992036699706767699157860904798957505081143747312911246515350313735031397786562111474800728183906801552964415604114267221708014650503416371603814718203653991102167755222616117998692632503630077961754668397032445720874683416593177351139861390338743408903539745973060232
      •17ò÷•         # Compressed integer 17098251
            в        # Convert the large integer to Base-17098251 as list
             å       # Check for each if its in the ranged-list (1 if truthy; 0 if falsey)
.•...•               # Compressed string "benin eritrea tajikistan suriname kyrgyz gabon burkinafaso cotedivoire turkmenistan mauritania libya"
      #              # Split by spaces
       „af…a f:      # Replace "af" with "a f" (for "burkina faso")
       „di" d'i":    # Replace "di" with " d'i'" (for "cote d'ivoire")
                 `   # Push all strings as separated items to the stack
’...’                # Push dictionary string "russia0canada0united states0china0brazil0australia0india0argentina0kazakhstan0congo0algeria0saudi arabia0mexico0indonesia0sudan0ÿ0iran0mongolia0peru0chad0niger0angola0mali0south africa0colombia0ethiopia0bolivia0ÿ0egypt0tanzania0nigeria0venezuela0namibia0mozambique0pakistan0turkey0chile0zambia0myanmar0afghanistan0south sudan0somalia0central african republic0ukraine0madagascar0botswana0kenya0france0yemen0thailand0spain0ÿ0cameroon0papua new guinea0sweden0uzbekistan0morocco0iraq0greenland0paraguay0zimbabwe0norway0japan0germany0finland0vietnam0malaysia0ÿ0poland0oman0italy0philippines0ÿ0new zealand0ÿ0ecuador0guinea0united kingdom0uganda0ghana0romania0laos0guyana0belarus0ÿ0senegal0syria0cambodia0uruguay0ÿ0tunisia0bangladesh0nepal0ÿ0greece0nicaragua0north korea0malawi0ÿ0ÿ",
                     # where the `ÿ` are filled with the strings on the stack to form: "russia0canada0united states0china0brazil0australia0india0argentina0kazakhstan0congo0algeria0saudi arabia0mexico0indonesia0sudan0libya0iran0mongolia0peru0chad0niger0angola0mali0south africa0colombia0ethiopia0bolivia0mauritania0egypt0tanzania0nigeria0venezuela0namibia0mozambique0pakistan0turkey0chile0zambia0myanmar0afghanistan0south sudan0somalia0central african republic0ukraine0madagascar0botswana0kenya0france0yemen0thailand0spain0turkmenistan0cameroon0papua new guinea0sweden0uzbekistan0morocco0iraq0greenland0paraguay0zimbabwe0norway0japan0germany0finland0vietnam0malaysia0cote d'ivoire0poland0oman0italy0philippines0burkina faso0new zealand0gabon0ecuador0guinea0united kingdom0uganda0ghana0romania0laos0guyana0belarus0kyrgyz0senegal0syria0cambodia0uruguay0suriname0tunisia0bangladesh0nepal0tajikistan0greece0nicaragua0north korea0malawi0eritrea0benin"
 0¡                  # Split this by "0"
s                    # Swap to take the list of 0s and 1s again
 Ï                   # Only leave the strings which are truthy at the same index
                     # (and output the result implicitly)

```

See this 05AB1E tip of mine (sections *How to use the dictionary?*, *How to compress strings not part of the dictionary?*, *How to compress large integers?*, and *How to compress integer lists?*) to understand how the compression parts work.
> 2 votes

# Answer
# 1. Python 3.5, 1651 1458 1398 bytes

Script takes two arguments. Lists are compressed using LZMA BZ2 zlib, encoded to Ascii85 and stored as two comment lines after fileheader. Script reads itself, decode and uncompress these lines.

```
#!/usr/bin/python3
#GhO`I6%\,>%(lBO\a@"&E!__Y)$A-Ff<:j\Zp8G1Q=R\[aL$##cd[#Pij[XO8YuBARE6=2nKRD/).0>%g#JDN88bcljG2%`4dgK<6&DcfL6B^8a,Q'!/kQ'%Y-V9;b`T;[FBm3&5T5Ys2U;CmXCF5:aq71_o,S+(:/uX&2L\fa_-/Kd'3s6'[G]sCn=J+=>6L_s/WA*`k@\':,lZ\ajllj%bUG0!qCp9F]27HBY(^&g;oVer&mCo)2`N/hX]II^\`uAc4tBW-9;`g,5d;uq]U>#PY..CpNFN`coGkC/^iJ/obu7<Xd,P9mG+g'N^u=3rEV<?>g(ktsJ*-0h`)JN0Qd/g$HOCkHOS9NOk5I@9mZQ(AT,&:D;D=6G:^[[=SHh;43Hhl.<kEAOiIW\\PrK;#`D?:k8qUU%%3@#\g19gTi`i0D3F,XH+;50n"r1ef9*)"a%bqYamDW(>P'r!bI:.gVAFJm8ke"\jNT^XS'D6lJVC=QibmBbdYu]A8q<$V4oh+DO0HR653:K@ZfLgC/3eQ1hYB;?.Jjffo6Hki<jQp>/o`2CO`l:75X50!JL1D.3e=%;ln5E%^0_p`^=LEEs0IQl*(,e5p
#GhOI,<t5?f#XeVP%DCQs@Uj%oUjWTD(l41.HE#\:p4+)_#$1Vhad1Jm5*P-3'#*CKij5)RT]`;4pYs(Neg<]+lVk(SN$V1O9Pimd<c%%.IW.a[YSm[1ht!C1:I<SVjZTUuYN)7^7#D((KD4T-=AM;V^T&UWbMi,>Ya\!/(t[6!A*tabY2Lt='tB`J]`oHWl03e4Qa=fZMu[=U-hfuQCD>b8o=4o2"T](^/'MZsb3+#T@&p,HQpC)FCec9Pc,M&NdXUa=S#I(4#dd3;6_)*Z5X]!WZ\%VJ@B<m-&^)`PH9K1r2i(<4Qn2P8MFP!EJj1eD\H@e>m"$h-X4`AC]fg"I/tPODfK,?*5Ru-l`$`>#lJhuVj.;nHE<`u/&mBdGT\n$Vp'4N#:<19D9Z+4@P<2aQG[ohN)/bpcZ+ghPo`GO.K*_
from base64 import*;from zlib import decompress;from sys import*;(f,t)=[*map(int,argv[1:3])];g=open(argv[0],"r");l=g.readlines();g.close()
def d(l,n):return decompress(a85decode(l[n][1:-1])).decode().split("\n")
n=d(l,1);a=d(l,2);o=[]
for i,b in enumerate(a):
    if f<=int(b)<=t:o.append(n[i])
print("{},{}\t->\t{}".format(f,t,", ".join(o)))

```

I know, it's not pretty to abuse comments like this. But it works... for golfing. To include binary data in text file you need to encode it to printable chars only. But base64 encoding is not dense enough, that is why I used A85. But it has chars that need to be escaped in order to put this in python string.. So then I use comments :)

## Explanation

```
# imports
from base64 import*
from zlib import decompress
from sys import*

# parse input as integers
(f,t)=[*map(int,argv[1:3])]

# open this file and read all lines
g=open(argv[0],"r");l=g.readlines();g.close()

# from array of lines get line n; strip leading "#" and trailing "\n"; decode from Ascii85; decompress; decode from bytes to string; split on newline
def d(l,n):return decompress(a85decode(l[n][1:-1])).decode().split("\n")

# decode list of names, list of areas and create empty output list
n=d(l,1);a=d(l,2);o=[]

# cycle through list of areas
for i,b in enumerate(a):

    # if curent area is between limits, append country to output list
    if f<=int(b)<=t:o.append(n[i])

# print formatted output
print("{},{}\t->\t{}".format(f,t,", ".join(o)))

```

edit: changed compression method and removed map(int) before enumerate

https://docs.python.org/3/library/zlib.html
> 2 votes

# Answer
# Jelly, 736 bytes

```
“þṾṚSẸL£ỵƘhŀẠṗµA+QØḣœḢpṗżÐEn⁷ȦyẈ⁷g%v3ọṇ(Ƥd>OṾTṭAJẓṛṢƊƭḟ¢ẊȦ9c°ÐṄ5IqżQo⁾Ṣæṗʂ"OƥkpṙY!e}Q/ẆⱮṠyṄ0ØȥLYỊṃ~+æ+İbɠṇxƊƁjjtẓ?ạ5ỌżṆiⱮẆj/ȯ¬ẉ⁹Œ¿żÐX¥hẇyqJ~⁶Żḟ#1QJṗ¹n³H.ḋ(Ṣ^ỊẆKḲŒU[⁵6¢2ȯdG/⁼ṭḥİ!ƈ3ḤḳUıHṇlṄ⁽€ẆṠwẈƁḣḳµ!⁾³Ḋ¦Ṭḳ0ƈØʠ⁴æ?+Ịṙ4⁸8Żḅ| GḅɗṆĠKİb"ḃɲʠµY⁴ḟnỊẋ⁺V³ṚĖıknṠƊMeẓƬḌ⁺£©9⁴ȥøẓɦ&7ɱ_2ɠȷṂẋṚcṇṫḢ)MȮ¶I7ıṃ1LŻỌƊḞYrỴȦṠṣ3ḥ<Ƥ½’ḃ“¡æ⁽ż’e€³rƝḢ¤Tị“Ṇ¹zẏƥKDTịAjṇẒ¤<Ṁ6:-jOʂƑṆɠw@Ẉṙ]Ż§!œ~Cıu",©ḳṂƒḥ¢Ė~,ḲsĿỊƭṀjⱮḳ%o!Ðrḍ3©ƊZØq-JṪƤƘÑẹ04ⱮṂṛ'÷ƥÆƁ¦z¢Ẓ3kaṁ⁾ẏHnĊ^ḍỤfçÄŒṅṣḍƒb ybḤċÄæ¬).sḋ ėmẸeHẈŀ⁺U®`nɓƙt ZeNH+¥ḋỌLYÑ¥ḳƬȤƘ³ẓ½⁸¢ṛŻḍ\ƙß³ÞdȦḲµṫk¡ẓ⁶ẒṠƑ~ġ+=3þḌ÷z⁾ñ9cø.'3ṆN⁸0HḟN+ƒN⁼ƁKạṪƲ⁽żė@ÑṣT³ṠQƁ1ṭ©>]Ɱr&Ị}°rð0ċ4ntėṭiḣƤ^/æmẠ8ZṪ®$ÄOẏ¬⁻v!ƭh]ḟÄF^Ẇß2Ɗ8þṄÆ⁴)ƒṛ⁺ƭ©ẹẓÑ3⁵|F}ß8"ÞḂṣ⁷%ƙ9Ɱ:D¥ĖĠÆ7ƒṭṘ³ɓċ³ɱTƊDɼ>Ɗ;ẹẇÐƒµcKṁ⁺ḳRỤ®+®lUṛ½ẒʂƊḃNʋḥæṠḤmḲ³ɓÑ`Ɲṗ[]ṠȮẏ3lḍƤʂXṃ4#ʠ°µḄƈẈıḥıẉ®×ḊẈƝỤġOlṠÆU½ẏ½ċƒµKRW»Ỵ¤K

```

Try it online!
> 1 votes

# Answer
# , 1656 bytes

```
function(a,b)d$s[d$c>=a&d$c<=b];d=data.frame(strsplit("russia,canada,united states,china,brazil,australia,india,argentina,kazakhstan,congo,algeria,saudi arabia,mexico,indonesia,sudan,libya,iran,mongolia,peru,chad,niger,angola,mali,south africa,colombia,ethiopia,bolivia,mauritania,egypt,tanzania,nigeria,venezuela,namibia,mozambique,pakistan,turkey,chile,zambia,myanmar,afghanistan,south sudan,somalia,central african republic,ukraine,madagascar,botswana,kenya,france,yemen,thailand,spain,turkmenistan,cameroon,papua new guinea,sweden,uzbekistan,morocco,iraq,greenland,paraguay,zimbabwe,norway,japan,germany,finland,vietnam,malaysia,cote d'ivoire,poland,oman,italy,philippines,burkina faso,new zealand,gabon,ecuador,guinea,united kingdom,uganda,ghana,romania,laos,guyana,belarus,kyrgyz,senegal,syria,cambodia,uruguay,suriname,tunisia,bangladesh,nepal,tajikistan,greece,nicaragua,north korea,malawi,eritrea,benin",',')[[1]],c(17098250,9984670,9831510,9562911,8515770,7741220,3287259,2780400,2724902,2686860,2381740,2149690,1964380,1910931,1879358,1759540,1745150,1564120,1285220,1284000,1267000,1246700,1240190,1219090,1141749,1104300,1098580,1030700,1001450,947300,923770,912050,824290,799380,796100,785350,756096,752610,676590,652860,644330,637660,622980,603550,587295,581730,580370,549087,527970,513120,505940,488100,475440,462840,447420,447400,446550,435050,410450,406752,390760,385178,377962,357380,338420,330967,330800,322460,312680,309500,301340,300000,274220,267710,267670,256370,245860,243610,241550,238540,238390,236800,214970,207600,199949,196710,185180,181040,176220,163820,163610,147630,147180,141376,131960,130370,120540,118480,117600,114760))

```

Try it online!
> 1 votes

---
Tags: code-golf, string, number, compression
---