# Question
Title: It's not who votes that counts; it's who counts the votes
# The scenario

You live in a country that is having a presidential election. Each voter gets one vote, and therefore there is a firmly-entrenched two-party system. (Third parties exist, but get hardly any votes).

The latest opinion poll shows the race in a dead heat:

* 49%: Alberto Arbusto
* 49%: Jorge Sangre
* 2%: various minor candidates

# The program requirements

You have been hired by the government to write part of the vote counting software. You will be given, on standard input, an unordered list of one precinct’s votes, one per line, like this:

```
Alberto Arbusto
Jorge Sangre
Jorge Sangre
Alberto Arbusto
Jorge Sangre
Alberto Arbusto
Alberto Arbusto
Jorge Sangre
Juan Perez
Jorge Sangre
Alberto Arbusto
Alberto Arbusto
…

```

and, after it has read all the votes, outputs a summary of how many votes each candidate got, sorted in descending order by number of votes, like this:

```
492 Jorge Sangre
484 Alberto Arbusto
 18 Juan Perez
  6 Mickey Mouse

```

# The underhanded part

You're a partisan hack who wants to steal the election for one of the two main candidates (you can choose which one). So, your program must deliberately print *incorrect* vote counts, with a systematic bias towards your favorite candidate.

Of course, you must do this is such a way that a person looking at your code or its output would likely not recognize the incorrect behavior.

# Answer
# Scala

Long live Alberto Arbusto!

```
import scala.io.Source
import java.util.concurrent.atomic.LongAdder

object Votes extends App {
  val votes = Source.stdin.getLines.toIndexedSeq
  val registeredCandidates = Seq(
    "Alberto Arbusto",
    "Juan Perez",
    "Mickey Mouse",
    "Jorge Sangre"
  )

  val summaries = registeredCandidates map (Summary.apply(_, new LongAdder))

  var currentCandidate: String = _

  for (vote <- votes.par) {
    currentCandidate = vote
    summaries.find(s => s.candidate == currentCandidate).map(_.total.increment)
  }

  for (summary <- summaries.sortBy(-_.total.longValue)) {
    println(summary)
  }
}

case class Summary(candidate: String, total: LongAdder) {
  override def toString = s"${total.longValue} ${candidate}"
}

```

Alberto Arbusto will almost always come out slightly ahead of Jorge Sangre, provided enough votes are cast (~10,000). There's no need to tamper with the votes themselves.

> There's a race condition. And by putting Alberto Arbusto earlier in the list, we increase his chances of winning the race.

Side note: This code is loosely based on a "custom" connection pool that I encountered on a project. It took us weeks to figure out why the application was perpetually out of connections.
> 34 votes

# Answer
# Ruby

```
vote_counts = $<.readlines.group_by{|s|s}.collect{ |name, votes| [votes.count, name] }

formatted_count_strings = vote_counts.map do |row,
  formatter = PrettyString.new|"%#{formatter[1][/[so]/]||'s'} %s"%
  [row,formatter]
end

sorted_count_strings = formatted_count_strings.sort_by(&:to_i).reverse

puts sorted_count_strings

```

Jorge Sangre will get a substantial boost in his vote count (for example, 492 votes will be reported as 754). Alberto's votes will be reported accurately.

> As you might guess, it's not who counts the votes but who formats the votes. I've tried to obscure it (`PrettyString.new` isn't a real thing and never gets called), but `formatter` is actually the name string. If the second letter of the name is 'o', the vote count will be printed out in octal instead of decimal.
> 16 votes

# Answer
# Bash

(Does this meet the specification?)

```
uniq -c|sort -rk2,2|uniq -f1|sort -gr

```

As always, this takes extra precautions to ensure valid output.

`uniq -c` prefixes each line with the number of times it occurs. This basically does all the work.

Just in case `uniq -c` does something wrong, we now sort its output by the names of candidates in reverse order, then run it through `uniq -f1` (don't print duplicate lines, ignoring the first field \[the number of votes\]) to remove any duplicate candidates. Finally we use `sort -gr` to sort in "General Numeric" and "Reverse" order (descending order by number of votes).

> `uniq -c` counts consecutive occurences, not occurences over the whole file. The winner will be the candidate with the most consecutive votes.
> 9 votes

# Answer
# C#

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        var candidates = new SortedDictionary<string, int>();
        string candidate;
        using (var sr = new StreamReader("candidates.txt"))
        {
            while ((candidate = sr.ReadLine()) != null)
            {
                if (candidates.ContainsKey(candidate))
                    candidates[candidate]++;
                else
                    candidates.Add(candidate, 1);
            }
        }

        // order by the votes
        var votes = candidates.OrderByDescending(k => k.Value).Select(x => x.Value);

        Console.WriteLine("Candidate | Votes");
        for (int i = 0; i < candidates.Count; i++)
        {
            Console.WriteLine(candidates.ElementAt(i).Key + " " + votes.ElementAt(i));
        }

        Console.ReadKey();
    }
}

```

The first candidate in the text file will always win!

It will make *Alberto Arbusto* the winner!

> The candidates' names are ordered alphabetically in the dictionary, but the votes are ordered by number.
> 8 votes

# Answer
# C

```
#include <stdio.h>

#define NCANDIDATES 4
static const char * const cand_list[NCANDIDATES] = {
    "Alberto Arbusto",
    "Juan Perez",
    "Mickey Mouse",
    "Jorge Sangre"
};

#define BUFFER_SIZE 100

int
main(int argc, char **argv)
{
    int votes[NCANDIDATES];
    int candidate;
    size_t name_start;
    int i;
    int j;
    int place;
    int max;
    size_t bytes;
    char buffer[BUFFER_SIZE];

    /*
    Make sure input is read in text mode, so we don't have to
    worry about whether line endings are LF or CRLF.
    */
    freopen(NULL, "rt", stdin);

    /* Initialize vote tally. */
    for (candidate = 0; candidate < NCANDIDATES; candidate++) {
        votes[candidate] = 0;
    }

    /* Read and process vote file. */
    do {
        /* Read a block of data. */
        bytes = fread(buffer, 1, BUFFER_SIZE, stdin);

        /* Loop over the data, finding and counting the votes. */
        name_start = 0;
        for (i = 0; i < bytes; i++) {
            if (buffer[i] == '\n') {
                /* Found name. */
                buffer[i] = '\0'; // nul-terminate name so strcmp will work
                /* Look up candidate. */
                for (j = 0; j < NCANDIDATES; j++) {
                    if (strcmp(&buffer[name_start], cand_list[j]) == 0) {
                        candidate = j;
                        break;
                    }
                }
                /* Count vote. */
                ++votes[candidate];

                /* Next name starts at next character */
                name_start = i + 1;
            }
        }
    } while (bytes > 0);

    /* Output the candidates, in decreasing order of votes. */
    for (place = 0; place < NCANDIDATES; place++) {
        max = -1;
        for (j = 0; j < NCANDIDATES; j++) {
            if (votes[j] > max) {
                candidate = j;
                max = votes[j];
            }
        }
        printf("%8d %s\n", votes[candidate], cand_list[candidate]);
        votes[candidate] = -1; // Remove from consideration for next place.
    }

    return 0;
}

```

Favors Jorge Sangre.

In testing with randomly generated vote files, even when Alberto Arbusto receives up to 1.4% more of the actual votes (49.7% vs 48.3% for Jorge Sangre), my man Jorge Sangre usually wins the count.

> Reading the data in fixed-size blocks often splits a line across two blocks. The fragment of the line at the end of the first block doesn't get counted because it doesn't have a newline character. The fragment in the second block does generate a vote, but it doesn't match any of the candidate's names so the 'candidate' variable doesn't get updated. This has the effect of transferring a vote from the candidate whose name was split to the candidate who received the previous vote. A longer name is more likely to be split across blocks, so Alberto Arbusto ends up being a vote "donor" more often than Jorge Sangre does.
> 7 votes

# Answer
## Python

```
from collections import defaultdict

def count_votes(candidate, votes=defaultdict(int)):
    with open('votes.txt') as f:
        for line in f:
            votes[line.strip()] += 1

    return votes[candidate]

if __name__ == '__main__':
    candidates = [
        'Mickey Mouse',
        'Juan Perez',
        'Alberto Arbusto',
        'Jorge Sangre'
    ]

    results = {candidate: count_votes(candidate) for candidate in candidates}

    for candidate in sorted(results, key=results.get, reverse=True):
        print results[candidate], candidate

```

The vote counts will favour candidates closer to the end of the list.

> In Python, mutable default arguments are created and bound to the function at definition. So the votes will be maintained between function calls and carried over for subsequent candidates. The number of votes will be counted twice for the second candidate, three times for the third, and so on.
> 5 votes

# Answer
## tr | sed | dc

```
tr ' [:upper:]' '\n[:lower:]' <votes |\
sed -e '1i0sa0ss0sp' -e \
    '/^[asp]/!d;s/\(.\).*/l\1 1+s\1/
    ${p;c[Alberto Arbusto: ]P lap[Jorge Sangre: ]P lsp[Juan Perez: ]P lpp
    }' | dc

```

This counts my buddy Alberto twice every time.

*"Oh - `tr`? Well, it's just necessary because computers aren't very good with capital letters - better if they're all lowercase.... Yeah, I know, computers are crazy."*

### OUTPUT

```
Alberto Arbusto: 12
Jorge Sangre: 5
Juan Perez: 1

```

Here's another version that gives Juan Perez's vote to Jorge Sangre:

```
tr '[:upper:]' '[:lower:]' <votes |\
sed -e '1i0sj0sa1so' -e \
    's/\(.\).*/l\1 1+s\1/
    ${p;c[Alberto Arbusto: ]P lap[Jorge Sangre: ]P ljp[Others: ]P lop
    }' | dc

```

### OUTPUT

```
Alberto Arbusto: 6
Jorge Sangre: 6
Others: 1

```
> 0 votes

# Answer
## **JavaScript**

```
    function Election(noOfVoters) {
    candidates = ["Albert", "Jorge", "Tony", "Chip"];
    votes = [];

    for (i = 1; i <= noOfVoters; i++) {

        votes.push(prompt("1 - Albert, 2 - Jorge, 3 - Tony , 4 - Chip"))

    }
    votes.sort();
    WinningOrder = count(votes);

    var placement = [];

    for (x = 0; x < candidates.length; x++) {
        placement.push(x + " place with " + WinningOrder[x] + " votes is " + candidates[x] + "\n");
    }
    placement.reverse();
    alert(placement)
}

function count(arr) {
    var a = [],
        b = [],
        prev;

    arr.sort();
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] !== prev) {
            a.push(arr[i]);
            b.push(1);
        } else {
            b[b.length - 1]++;
        }
        prev = arr[i];
    }

    b.sort();

    return b;
}

```

The last person in the candidates list will always win.
> 0 votes

---
Tags: popularity-contest, underhanded
---


# Question
Title: Minimal cover of bases for quadratic residue testing of squareness
## Challenge

Find the smallest cover of bases (e.g., moduli) whose sets of quadratic residue can be tested via table-lookup to definitively determine whether or not a given non-negative integer *n* is a perfect square. The bases must all be less than or equal to the square root of the maximum value of *n*.

The answer with the smallest set of bases for a given category of *n* wins the challenge. (This means there may potentially be more than one winner.) The categories of *n* are:

```
         Category       Maximum allowed n    Maximum allowed modulus/base
    -------------    --------------------    ----------------------------
     8-bit values                     255                              15
    16-bit values                   65535                             255
    32-bit values              4294967295                           65535
    64-bit values    18446744073709551615                      4294967295

```

In the event of a tie with two sets having equal cardinality, the tie will go to the set having the greater ability to detect non-squares earlier in the sequence.

In the event that no complete covers are found (which is entirely likely for the 32-bit and 64-bit categories), the winner will be the set of bases which statistically or provably rules out the highest percentage of non-squares (without incorrectly reporting squares as non-squares). See below for a discussion of incomplete covers.

## Background

In many number theory applications, the question arises whether or not some number *n* is a perfect square (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, etc.). One way to test whether *n* is square is to test whether floor(√n)² = n, that is, whether the rounded-down square root of *n*, when squared, gives back *n*. For example, floor(√123)² = 11² = 121, which is not 123, so 123 is not square; but floor(√121)² = 11² = 121, so 121 is square. This method works fine for small numbers, especially when a hardware square-root operation is available. But for large numbers (hundreds or thousands of bits) it can be very slow.

Another way to test for squareness is to rule out non-squares using quadratic residue tables. For example, all squares in base 10 must have a final (ones-place) digit that is either 0, 1, 4, 5, 6, or 9. These values form the set of quadratic residue for base 10. So if a base-10 number ends in 0, 1, 4, 5, 6, or 9, you know that it *might* be square, and further examination will be required. But if a base-10 number ends in 2, 3, 7, or 8, then you can be *certain* that it is *not* square.

So let's look at another base. All squares in base 8 must end in 0, 1, or 4, which conveniently is only 3 of 8 possibilities, meaning a 37.5% chance of a random number being possibly square, or 62.5% chance of a random number definitely not being square. Those are much better odds than what base 10 gives. (And note that a base-8 modulus operation is simply a logical-and operation, as opposed to base-10 modulus, which is a division by 10 with remainder.)

Are there even better bases? Well, yes, actually. Base 120 has 18 possibilities (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100, and 105), which represents only a 15% chance of possibly being square. And base 240 is better yet, with only 24 possibilities, representing only 10% chance of possibly being square.

But no single base alone can definitively determine squareness (unless it is larger than the maximum number being tested, which is eminently impractical). A single base alone can only *rule out* squareness; it cannot conclusively *verify* squareness. Only a carefully selected set of bases, working together, can conclusively verify squareness over a range of integers.

So, the question becomes: What set of bases forms a minimal cover which together permit the definitive deduction of squareness or non-squareness?

## Example of a correct but non-minimal cover

The cover 16-base cover { 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37 } is sufficient to definitively determine squareness or non-squareness of *all* 16-bit values 0 to 65535. But it is not a *minimal* cover, because at least one 15-base cover exists that is also easily discoverable. In fact, it is likely that far smaller covers exist — perhaps with as few as 6 or 7 bases.

But for illustration, let's take a look at testing a sample value of *n* using this 16-base cover set. Here are the sets of quadratic residues for the above set of bases:

```
Base m   Quadratic residue table specific to base m
------   ----------------------------------------------------
   3     {0,1}
   4     {0,1}
   5     {0,1,4}
   7     {0,1,2,4}
   8     {0,1,4}
   9     {0,1,4,7}
  11     {0,1,3,4,5,9}
  13     {0,1,3,4,9,10,12}
  16     {0,1,4,9}
  17     {0,1,2,4,8,9,13,15,16}
  19     {0,1,4,5,6,7,9,11,16,17}
  23     {0,1,2,3,4,6,8,9,12,13,16,18}
  25     {0,1,4,6,9,11,14,16,19,21,24}
  29     {0,1,4,5,6,7,9,13,16,20,22,23,24,25,28}
  31     {0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28}
  37     {0,1,3,4,7,9,10,11,12,16,21,25,26,27,28,30,33,34,36}

```

Now let's test the number *n* = 50401 using this set of bases, by converting it into each base. (This is not the most efficient way examine residue, but it is sufficient for explanatory purposes.) It's the 1's place that we're interested in here (marked below in parentheses):

```
 Base                               "Digits" in base m
   m          m^9   m^8   m^7   m^6   m^5   m^4   m^3   m^2   m^1  ( m^0 )
 ----      -----------------------------------------------------------------
   3           2     1     2     0     0     1     0     2     0   (  1 ) ✓
   4                       3     0     1     0     3     2     0   (  1 ) ✓
   5                             3     1     0     3     1     0   (  1 ) ✓
   7                                   2     6     6     6     4   (  1 ) ✓
   8                                   1     4     2     3     4   (  1 ) ✓
   9                                         7     6     1     2   (  1 ) ✓
  11                                         3     4     9     5   ( 10 )
  13                                         1     9    12     3   (  0 ) ✓
  16                                              12     4    14   (  1 ) ✓
  17                                              10     4     6   ( 13 ) ✓
  19                                               7     6    11   ( 13 )
  23                                               4     3     6   (  8 ) ✓
  25                                               3     5    16   (  1 ) ✓
  29                                               2     1    26   ( 28 ) ✓
  31                                               1    21    13   ( 26 )
  37                                                    36    30   (  7 ) ✓

```

So we can see that in 13 of these bases, the residue matches a known quadratic residue (call this a "hit" in the table), and in 3 of these bases, the residue does not match a known quadratic residue (call this a "miss"). All it takes is 1 miss to know that a number is non-square, so we could stop at 11, but for illustrative purposes, we've examined all 16 of the bases here.

## Example of an incomplete cover

Technically, an incomplete cover is not a cover, but that's beside the point. The set of bases { 7, 8, 11, 15 } *nearly* covers all the 8-bit values of *n* from 0 to 255 correctly, but not quite. In particular, it incorrectly identifies 60 and 240 as being square (these are false positives) — but it does correctly identify all of the actual squares (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, and 225) and makes no other false positives. So this is a 4-set which almost succeeds as a solution, but ultimately fails, because an incomplete cover is not a valid solution.

For 8-bit *n*, the set of bases { 7, 8, 11, 15 } is one of two sets of 4 bases which produce two errors, and there are seven sets of 4 bases which only produce one error. No sets of 4 bases actually exist which form a complete and accurate cover of 8-bit values. Can you find a set of 5 bases which produce no errors, covering all 8-bit values correctly? Or do you need 6 or more? (I do know the answer for 8-bit *n*, but I'm not going to give it away. I do not know the answer for 16-bit, 32-bit, or 64-bit, and I believe even the 16-bit case is impossible to solve via brute-force searching. Solving the 32-bit and 64-bit cases will certainly require genetic, heuristic, or other search techniques.)

## A comment on cryptographically large numbers

Beyond 64-bit numbers — up in the hundreds or thousands of binary digits — this is where a quick squareness check really comes in most handy, even if the cover is incomplete (which it most certainly will be for really large numbers). How could a test like this still be useful even if it is insufficiently decisive? Well, imagine you had an extremely fast test for squareness which worked correctly 99.9% of the time and gave false negatives the remaining 0.1% of the time and never gave false positives. With such a test, you would be able to determine non-squareness of a number nearly instantly, and then in the exceptional cases of indecisiveness, you could then resort to a slower method to resolve the unknown a different way. This would save you quite a bit of time.

For example, the set { 8, 11, 13, 15 } is correct 99.61% of the time for 8-bit values of *n* from 0 to 255, is correct 95.98% of the time for 16-bit values of *n* from 0 to 65535, and is correct 95.62% of the time for 24-bit values of *n* from 0 to 16777215. As *n* goes to infinity, the percentage of correctness for this set of bases goes down, but it asymptotically approaches and never drops below 95.5944% correctness.

So even this very tiny set of 4 small bases is useful to nearly immediately identify about 22 out of 23 arbitrarily large numbers as being non-squares — obviating the need for further inspection of those numbers by slower methods. The slower methods then need only be applied in the small percentage of cases which could not be ruled out by this quick test.

It is interesting to note that some 16-bit bases achieve better than 95% all on their own. In fact, each of the bases below is able to weed out better than 97% of all numbers up to infinity as not being square. The quadratic residue set for each of these bases can be represented as a packed-bit array using only 8192 bytes.

Here are the 10 most powerful single bases less than 2^16:

```
 Rank   Base    Prime factorization       Weeds out
 ----   ------------------------------    ---------
  1.    65520 = 2^4 x 3^2 x 5 x 7 x 13      97.95%
  2.    55440 = 2^4 x 3^2 x 5 x 7 x 11      97.92%
  3.    50400 = 2^5 x 3^2 x 5^2 x 7         97.56%
  4.    52416 = 2^6 x 3^2 x 7 x 13          97.44%
  5.    61200 = 2^4 x 3^2 x 5^2 x 17        97.41%
  6.    44352 = 2^6 x 3^2 x 7 x 11          97.40%
  7.    63360 = 2^7 x 3^2 x 5 x 11          97.39%
  8.    60480 = 2^6 x 3^3 x 5 x 7           97.38%
  9.    63840 = 2^5 x 3 x 5 x 7 x 19        97.37%
 10.    54720 = 2^6 x 3^2 x 5 x 19          97.37%

```

See anything interesting that these bases all have in common? There's no reason to think they might be useful in combination together (maybe they are, maybe they aren't), but there are some good clues here as to what bases are likely to be most influential for the larger categories of numbers.

**Side challenge:** One of the most influential bases (if not *the* most) up to 2^28 is 245044800, which alone can correctly weed out 99.67% of non-squares, or about 306 of 307 random numbers thrown at it. Can you find *the* most influential single base less than 2^32?

## Related

There are some very nice ideas in the following questions that are closely related, as well as several micro-optimization tricks for making certain operations faster. Although the linked questions do not specifically set out to find the strongest set of bases, the idea of strong bases is implicitly central some of the optimization techniques used there.

# Answer
> 7 votes
## Mathematica

I don't really know a lot about number theory (unfortunately), so this is a rather naive approach. I'm using a greedy algorithm which always adds the base that has the most misses for the remaining numbers.

```
bits = 8
Timing[
 maxN = 2^bits - 1;
 maxBase = 2^(bits/2) - 1;
 bases = {
     #,
     Union[Mod[Range[0, Floor[#/2]]^2, #]]
     } & /@ Range[3, maxBase];
 bases = SortBy[bases, Length@#[[2]]/#[[1]] &];
 numbers = {};
 For[i = 0, i <= Quotient[maxN, bases[[1, 1]]], ++i,
  AppendTo[numbers, # + i*bases[[1, 1]]] & /@ bases[[1, 2]]
  ];
 While[numbers[[-1]] > maxN, numbers = Most@numbers];
 numbers = Rest@numbers;
 i = 0;
 cover = {bases[[1, 1]]};
 lcm = cover[[-1]];
 Print@cover[[1]];
 While[Length@numbers > maxBase,
  ++i;
  bases = DeleteCases[bases, {b_, r_} /; b\[Divides]lcm];
  (*bases=SortBy[bases,(Print[{#,c=Count[numbers,n_/;MemberQ[#[[2]],
  Mod[n,#[[1]]]]]}];c)&];*)
  bases = SortBy[
    bases,
    (
      n = Cases[numbers, n_ /; n < LCM[#[[1]], lcm]];
      Count[n, n_ /; MemberQ[#[[2]], Mod[n, #[[1]]]]]/Length@n
      ) &
    ];
  {base, residues} = bases[[1]];
  numbers = Cases[numbers, n_ /; MemberQ[residues, Mod[n, base]]];
  AppendTo[cover, base];
  lcm = LCM[lcm, base];
  Print@base
  ];
 cover
 ]

```

It solves 8 bits in no time with the following 6 bases:

```
{12, 13, 7, 11, 5, 8}

```

16 bits takes 6s and results in the following 6-base cover:

```
{240, 247, 253, 119, 225, 37}

```

For the larger cases this approach obviously runs out of memory.

To go beyond 16 bit, I'll need to figure out a way to check for a cover to be complete without actually keeping a list of all numbers up to Nmax (or go and learn about number theory).

**Edit:** Reduced runtime for 16 bits from 66s to 8s by prepopulating the list of numbers with only those which are not ruled out by the most effective base. This should also significantly improve the memory footprint.

**Edit:** I added two minor optimisations to reduce the search space. It's not one of the official categories, but with that I found an 8-base cover for 24 bits in 9.3 hours:

```
{4032, 3575, 4087, 3977, 437, 899, 1961, 799}

```

As for the optimisations, I am now skipping all bases which divide the LCM of the bases already in the cover, and when I test a base's efficiency I only test it against numbers up to the LCM of that new base and all the bases I already have.

---
Tags: code-challenge, arithmetic, number-theory
---


# Question
Title: Programming Praxis - Survive like Flavius Josephus
Here's a challenge inspired by Programming Praxis:

http://programmingpraxis.com/2009/02/19/flavius-josephus/

> Write a function josephus(n,m) that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed, every mth person in turn, with the sole survivor as the last person in the list.

Example output:

> josephus(41,3)
>
> 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30

The function can't leak on the global scope, and must return a list or an array.

If your language can't return an array, it is allowed to just print the list.

Shortest answer (in bytes) wins.

# Answer
**Python 2 (85 Bytes):**

Thanks to bitpwner we have this solution:

```
def j(m,n):
    a,b,c=range(m),0,[]
    while a:b=(b+n-1)%len(a);c+=[a.pop(b)]
    return c

```

To use this in Python 3 you have to cast `a` to a list, this comes with the cost of another 6 bytes.

**Python 3 (114 bytes):**

This was my first thought, but I think this is a good but no perfect solution:

```
def j(m,n):
    a,b=__import__("collections").deque(range(m)),[]
    while a:a.rotate(-n);b.append(a.pop())
    return b

```

I was not happy with the use of the deque, but I couldn't think of any other solution. At least I could save 5 bytes with `__import__`.

This function works as described above, `a` are the people and `b` is the execution order. As long as there are still people left (`while a:`), it rotates the deque/the people by `n` and appends the current man (`a.pop()`) to the execution list.
> 3 votes

# Answer
## Haskell, 79 ~~83~~ characters

I still think mutable state could triumph if this is reopened, but recursion holds its own for now.

Edit: Following proud haskeller's suggestions shaves off another 4 characters.

```
j n m=f[0..n-1][]1where f[]k _=k;f(a:b)k t|m==t=f b(k++[a])1|0<1=f(b++[a])k$t+1

```

Pre-suggestions:

```
j n m=f[][0..n-1]$1 where f k[]_=k;f k(a:b)t|m==t=f(k++[a])b 1|0<1=f k(b++[a])(t+1)

```

### Haskell, 111 characters

First attempt:

```
j n m=reverse.snd.foldl f(0,[]).take(n*n).cycle$[0..n-1]where f a@(t,d)x|x`elem`d=a|t+1==m=(0,x:d)|True=(t+1,d)

```
> 1 votes

# Answer
# \>\<\> \- 46

Really wanted to \>\<\> a shot on this one, but unfortunately \>\<\> has no concept of returning an array, so I simply printed it instead.

```
|v-1&
->: ?!\:1
>?!;ao>&:&\
^ln~\
1)?!/$}1- >:

```

Explanation:

`|v-1&` loads the second argument into the register and subtracts 1 from the first argument

`->: ?!\:1` unrolls the second argument so the stack has every value between it and 0 (so 5 becomes 5, 4, 3, 2, 1, 0)

`>?!;ao>&:&\
^ln~\` has two distinct parts. `&:&\` clones the value in the register onto the top of the stack, and the rest simply prints the top value on the stack, and ends the program if there's nothing left.

`)?!/$}1- >:` rotates the whole stack as many times as the top value, which is what we copied from the register earlier.
> 1 votes

# Answer
# Python 2, 96 95 bytes

Since the obvious way to do it in Python was already taken, I had to do it recursively. :)

```
r=range
x=lambda o,l,m:l and x(o+l[:1],l[m:]+l[1:m],m)or o
j=lambda n,m:x([],r(m-1,n)+r(m-1),m)

```
> 0 votes

# Answer
## Perl - 94 Bytes

```
sub j{my$a=pop;my@c=((my$i=0)..pop()-1);while(@c){push@_,splice(@c,$i=($i+$a-1)%@c,1)}return@_}

```
> 0 votes

# Answer
# Matlab (90)

```
function l=j(n,m)
a=0:n-1;l=[];j=m;for i=a;l=[l,a(j)];a(j)=[];j=mod(j+m-2,length(a))+1;end

```
> 0 votes

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