Fairshare between two and more
You are encouraged to solve this task according to the task description, using any language you may know.
The Thue-Morse sequence is a sequence of ones and zeros that if two people take turns in the given order, the first persons turn for every '0' in the sequence, the second for every '1'; then this is shown to give a fairer, more equitable sharing of resources. (Football penalty shoot-outs for example, might not favour the team that goes first as much if the penalty takers take turns according to the Thue-Morse sequence and took 2^n penalties)
The Thue-Morse sequence of ones-and-zeroes can be generated by:
- "When counting in binary, the digit sum modulo 2 is the Thue-Morse sequence"
- Sharing fairly between two or more
Use this method:
- When counting base b, the digit sum modulo b is the Thue-Morse sequence of fairer sharing between b people.
- Task
Counting from zero; using a function/method/routine to express an integer count in base b, Sum the digits modulo b to produce the next member of the Thue-Morse fairshare series for b people.
Show the first 25 terms of the fairshare sequence
- For two people
- For three people
- For five people
- For eleven people
- References
- Non-decimal radices/Convert
- Thue-Morse
- A010060, A053838, A053840: The On-Line Encyclopedia of Integer Sequences® (OEIS®)
C
<lang c>#include <stdio.h>
- include <stdlib.h>
int turn(int base, int n) {
int sum = 0; while (n != 0) { int rem = n % base; n = n / base; sum += rem; } return sum % base;
}
void fairshare(int base, int count) {
int i;
printf("Base %2d:", base); for (i = 0; i < count; i++) { int t = turn(base, i); printf(" %2d", t); } printf("\n");
}
void turnCount(int base, int count) {
int *cnt = calloc(base, sizeof(int)); int i, minTurn, maxTurn, portion;
if (NULL == cnt) { printf("Failed to allocate space to determine the spread of turns.\n"); return; }
for (i = 0; i < count; i++) { int t = turn(base, i); cnt[t]++; }
minTurn = INT_MAX; maxTurn = INT_MIN; portion = 0; for (i = 0; i < base; i++) { if (cnt[i] > 0) { portion++; } if (cnt[i] < minTurn) { minTurn = cnt[i]; } if (cnt[i] > maxTurn) { maxTurn = cnt[i]; } }
printf(" With %d people: ", base); if (0 == minTurn) { printf("Only %d have a turn\n", portion); } else if (minTurn == maxTurn) { printf("%d\n", minTurn); } else { printf("%d or %d\n", minTurn, maxTurn); }
free(cnt);
}
int main() {
fairshare(2, 25); fairshare(3, 25); fairshare(5, 25); fairshare(11, 25);
printf("How many times does each get a turn in 50000 iterations?\n"); turnCount(191, 50000); turnCount(1377, 50000); turnCount(49999, 50000); turnCount(50000, 50000); turnCount(50001, 50000);
return 0;
}</lang>
- Output:
Base 2: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 Base 3: 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 Base 5: 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 Base 11: 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4 How many times does each get a turn in 50000 iterations? With 191 people: 261 or 262 With 1377 people: 36 or 37 With 49999 people: 1 or 2 With 50000 people: 1 With 50001 people: Only 50000 have a turn
Factor
<lang factor>USING: formatting kernel math math.parser sequences ;
- nth-fairshare ( n base -- m )
[ >base string>digits sum ] [ mod ] bi ;
- <fairshare> ( n base -- seq )
[ nth-fairshare ] curry { } map-integers ;
{ 2 3 5 11 } [ 25 over <fairshare> "%2d -> %u\n" printf ] each</lang>
- Output:
2 -> { 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 } 3 -> { 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 } 5 -> { 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 } 11 -> { 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4 }
Go
<lang go>package main
import (
"fmt" "sort" "strconv" "strings"
)
func fairshare(n, base int) []int {
res := make([]int, n) for i := 0; i < n; i++ { j := i sum := 0 for j > 0 { sum += j % base j /= base } res[i] = sum % base } return res
}
func turns(n int, fss []int) string {
m := make(map[int]int) for _, fs := range fss { m[fs]++ } m2 := make(map[int]int) for _, v := range m { m2[v]++ } res := []int{} sum := 0 for k, v := range m2 { sum += v res = append(res, k) } if sum != n { return fmt.Sprintf("only %d have a turn", sum) } sort.Ints(res) res2 := make([]string, len(res)) for i := range res { res2[i] = strconv.Itoa(res[i]) } return strings.Join(res2, " or ")
}
func main() {
for _, base := range []int{2, 3, 5, 11} { fmt.Printf("%2d : %2d\n", base, fairshare(25, base)) } fmt.Println("\nHow many times does each get a turn in 50000 iterations?") for _, base := range []int{191, 1377, 49999, 50000, 50001} { t := turns(base, fairshare(50000, base)) fmt.Printf(" With %d people: %s\n", base, t) }
}</lang>
- Output:
2 : [ 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0] 3 : [ 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1] 5 : [ 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3] 11 : [ 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4] How many times does each get a turn in 50000 iterations? With 191 people: 261 or 262 With 1377 people: 36 or 37 With 49999 people: 1 or 2 With 50000 people: 1 With 50001 people: only 50000 have a turn
Haskell
<lang haskell>import Data.List (intercalate, unfoldr) import Data.Tuple (swap) import Data.Bool (bool)
thueMorse :: Int -> [Int] thueMorse base = baseDigitsSumModBase base <$> [0 ..]
baseDigitsSumModBase :: Int -> Int -> Int baseDigitsSumModBase base n =
mod (sum (unfoldr ((bool Nothing . Just . swap . flip quotRem base) <*> (0 <)) n)) base
TEST----------------------------
main :: IO () main =
putStrLn $ fTable "First 25 fairshare terms for a given number of players:\n" show (('[' :) . (++ " ]") . intercalate "," . fmap (justifyRight 2 ' ' . show)) (take 25 . thueMorse) [2, 3, 5, 11]
DISPLAY--------------------------
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String fTable s xShow fxShow f xs =
unlines $ s : fmap (((++) . justifyRight w ' ' . xShow) <*> ((" -> " ++) . fxShow . f)) xs where w = maximum (length . xShow <$> xs)
justifyRight :: Int -> a -> [a] -> [a] justifyRight n c = (drop . length) <*> (replicate n c ++)</lang>
- Output:
First 25 fairshare terms for a given number of players: 2 -> [ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ] 3 -> [ 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 ] 5 -> [ 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 ] 11 -> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 0, 2, 3, 4 ]
J
fairshare=: [ | [: +/"1 #.inv 2 3 5 11 fairshare"0 1/i.25 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4 NB. In the 1st 50000 how many turns does each get? answered: <@({.,#)/.~"1 ] 2 3 5 11 fairshare"0 1/i.50000 +-------+-------+-------+-------+-------+------+------+------+------+------+-------+ |0 25000|1 25000| | | | | | | | | | +-------+-------+-------+-------+-------+------+------+------+------+------+-------+ |0 16667|1 16667|2 16666| | | | | | | | | +-------+-------+-------+-------+-------+------+------+------+------+------+-------+ |0 10000|1 10000|2 10000|3 10000|4 10000| | | | | | | +-------+-------+-------+-------+-------+------+------+------+------+------+-------+ |0 4545 |1 4545 |2 4545 |3 4545 |4 4546 |5 4546|6 4546|7 4546|8 4546|9 4545|10 4545| +-------+-------+-------+-------+-------+------+------+------+------+------+-------+
Java
<lang java> import java.util.ArrayList; import java.util.Arrays; import java.util.List;
public class FairshareBetweenTwoAndMore {
public static void main(String[] args) { for ( int base : Arrays.asList(2, 3, 5, 11) ) { System.out.printf("Base %d = %s%n", base, thueMorseSequence(25, base)); } } private static List<Integer> thueMorseSequence(int terms, int base) { List<Integer> sequence = new ArrayList<Integer>(); for ( int i = 0 ; i < terms ; i++ ) { int sum = 0; int n = i; while ( n > 0 ) { // Compute the digit sum sum += n % base; n /= base; } // Compute the digit sum module base. sequence.add(sum % base); } return sequence; }
} </lang>
- Output:
Base 2 = [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0] Base 3 = [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1] Base 5 = [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3] Base 11 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]
JavaScript
<lang javascript>(() => {
'use strict';
// thueMorse :: Int -> [Int] const thueMorse = base => // Thue-Morse sequence for a given base fmapGen(baseDigitsSumModBase(base))( enumFrom(0) )
// baseDigitsSumModBase :: Int -> Int -> Int const baseDigitsSumModBase = base => // For any integer n, the sum of its digits // in a given base, modulo that base. n => sum(unfoldl( x => 0 < x ? ( Just(quotRem(x)(base)) ) : Nothing() )(n)) % base
// ------------------------TEST------------------------ const main = () => console.log( fTable( 'First 25 fairshare terms for a given number of players:' )(str)( xs => '[' + map( compose(justifyRight(2)(' '), str) )(xs) + ' ]' )( compose(take(25), thueMorse) )([2, 3, 5, 11]) );
// -----------------GENERIC FUNCTIONS------------------
// Just :: a -> Maybe a const Just = x => ({ type: 'Maybe', Nothing: false, Just: x });
// Nothing :: Maybe a const Nothing = () => ({ type: 'Maybe', Nothing: true, });
// Tuple (,) :: a -> b -> (a, b) const Tuple = a => b => ({ type: 'Tuple', '0': a, '1': b, length: 2 });
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c const compose = (...fs) => x => fs.reduceRight((a, f) => f(a), x);
// enumFrom :: Enum a => a -> [a] function* enumFrom(x) { // A non-finite succession of enumerable // values, starting with the value x. let v = x; while (true) { yield v; v = 1 + v; } }
// fTable :: String -> (a -> String) -> (b -> String) // -> (a -> b) -> [a] -> String const fTable = s => xShow => fxShow => f => xs => { // Heading -> x display function -> // fx display function -> // f -> values -> tabular string const ys = xs.map(xShow), w = Math.max(...ys.map(length)); return s + '\n' + zipWith( a => b => a.padStart(w, ' ') + ' -> ' + b )(ys)( xs.map(x => fxShow(f(x))) ).join('\n'); };
// fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b] const fmapGen = f => function*(gen) { let v = take(1)(gen); while (0 < v.length) { yield(f(v[0])) v = take(1)(gen) } };
// justifyRight :: Int -> Char -> String -> String const justifyRight = n => // The string s, preceded by enough padding (with // the character c) to reach the string length n. c => s => n > s.length ? ( s.padStart(n, c) ) : s;
// length :: [a] -> Int const length = xs => // Returns Infinity over objects without finite // length. This enables zip and zipWith to choose // the shorter argument when one is non-finite, // like cycle, repeat etc (Array.isArray(xs) || 'string' === typeof xs) ? ( xs.length ) : Infinity;
// map :: (a -> b) -> [a] -> [b] const map = f => // The list obtained by applying f to each element of xs. // (The image of xs under f). xs => (Array.isArray(xs) ? ( xs ) : xs.split()).map(f);
// quotRem :: Int -> Int -> (Int, Int) const quotRem = m => n => Tuple(Math.floor(m / n))( m % n );
// str :: a -> String const str = x => x.toString();
// sum :: [Num] -> Num const sum = xs => // The numeric sum of all values in xs. xs.reduce((a, x) => a + x, 0);
// take :: Int -> [a] -> [a] // take :: Int -> String -> String const take = n => // The first n elements of a list, // string of characters, or stream. xs => 'GeneratorFunction' !== xs .constructor.constructor.name ? ( xs.slice(0, n) ) : [].concat.apply([], Array.from({ length: n }, () => { const x = xs.next(); return x.done ? [] : [x.value]; }));
// unfoldl :: (b -> Maybe (b, a)) -> b -> [a] const unfoldl = f => v => { // Dual to reduce or foldl. // Where these reduce a list to a summary value, unfoldl // builds a list from a seed value. // Where f returns Just(a, b), a is appended to the list, // and the residual b is used as the argument for the next // application of f. // Where f returns Nothing, the completed list is returned. let xr = [v, v], xs = []; while (true) { const mb = f(xr[0]); if (mb.Nothing) { return xs } else { xr = mb.Just; xs = [xr[1]].concat(xs); } } };
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] const zipWith = f => xs => ys => { const lng = Math.min(length(xs), length(ys)), vs = take(lng)(ys); return take(lng)(xs) .map((x, i) => f(x)(vs[i])); };
// MAIN --- return main();
})();</lang>
- Output:
First 25 fairshare terms for a given number of players: 2 -> [ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ] 3 -> [ 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 ] 5 -> [ 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 ] 11 -> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 0, 2, 3, 4 ]
Julia
<lang julia>fairshare(nplayers,len) = [sum(digits(n, base=nplayers)) % nplayers for n in 0:len-1]
for n in [2, 3, 5, 11]
println("Fairshare ", n > 2 ? "among" : "between", " $n people: ", fairshare(n, 25))
end
</lang>
- Output:
Fairshare between 2 people: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0] Fairshare among 3 people: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1] Fairshare among 5 people: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3] Fairshare among 11 people: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]
Perl
<lang perl>use strict; use warnings; use Math::AnyNum qw(sum polymod);
sub fairshare {
my($b, $n) = @_; sprintf '%3d'x$n, map { sum ( polymod($_, $b, $b )) % $b } 0 .. $n-1;
}
for (<2 3 5 11>) {
printf "%3s:%s\n", $_, fairshare($_, 25);
}</lang>
- Output:
2: 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 3: 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 5: 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 11: 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4
Perl 6
Add an extension showing the relative fairness correlation of this selection algorithm. An absolutely fair algorithm would have a correlation of 1 for each person (no person has an advantage or disadvantage due to an algorithmic artefact.) This algorithm is fair, and gets better the more iterations are done.
A lower correlation factor corresponds to an advantage, higher to a disadvantage, the closer to 1 it is, the fairer the algorithm. Absolute best possible advantage correlation is 0. Absolute worst is 2.
<lang perl6>sub fairshare (\b) { ^∞ .hyper.map: { .polymod( b xx * ).sum % b } }
.say for <2 3 5 11>.map: { .fmt('%2d:') ~ .&fairshare[^25]».fmt('%2d').join: ', ' }
say "\nRelative fairness of this method. Scaled fairness correlation. The closer to 1.0 each person is, the more fair the selection algorithm is. Gets better with more iterations.";
for <2 3 5 11 39> -> $people {
print "\n$people people: \n"; for $people * 1, $people * 10, $people * 1000 -> $iterations { my @fairness; fairshare($people)[^$iterations].kv.map: { @fairness[$^v % $people] += $^k } my $scale = @fairness.sum / @fairness; my @range = @fairness.map( { $_ / $scale } ); printf "After round %4d: Best advantage: %-10.8g - Worst disadvantage: %-10.8g - Spread between best and worst: %-10.8g\n", $iterations/$people, @range.min, @range.max, @range.max - @range.min; }
}</lang>
2: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 3: 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 5: 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4 Relative fairness of this method. Scaled fairness correlation. The closer to 1.0 each person is, the more fair the selection algorithm is. Gets better with more iterations. 2 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 After round 1000: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 3 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 0.99310345 - Worst disadvantage: 1.0068966 - Spread between best and worst: 0.013793103 After round 1000: Best advantage: 0.99999933 - Worst disadvantage: 1.0000007 - Spread between best and worst: 1.3337779e-06 5 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 After round 1000: Best advantage: 1 - Worst disadvantage: 1 - Spread between best and worst: 0 11 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 0.99082569 - Worst disadvantage: 1.0091743 - Spread between best and worst: 0.018348624 After round 1000: Best advantage: 0.99999909 - Worst disadvantage: 1.0000009 - Spread between best and worst: 1.8183471e-06 39 people: After round 1: Best advantage: 0 - Worst disadvantage: 2 - Spread between best and worst: 2 After round 10: Best advantage: 0.92544987 - Worst disadvantage: 1.0745501 - Spread between best and worst: 0.14910026 After round 1000: Best advantage: 0.99999103 - Worst disadvantage: 1.000009 - Spread between best and worst: 1.7949178e-05
Phix
<lang Phix>function fairshare(integer n, base)
sequence res = repeat(0,n) for i=1 to n do integer j = i-1, t = 0 while j>0 do t += remainder(j,base) j = floor(j/base) end while res[i] = remainder(t,base) end for return {base,res}
end function
constant tests = {2,3,5,11} for i=1 to length(tests) do
printf(1,"%2d : %v\n", fairshare(25, tests[i]))
end for</lang>
- Output:
2 : {0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0} 3 : {0,1,2,1,2,0,2,0,1,1,2,0,2,0,1,0,1,2,2,0,1,0,1,2,1} 5 : {0,1,2,3,4,1,2,3,4,0,2,3,4,0,1,3,4,0,1,2,4,0,1,2,3} 11 : {0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,0,2,3,4}
Python
Procedural
<lang python>from itertools import count, islice
def _basechange_int(num, b):
""" Return list of ints representing positive num in base b
>>> b = 3 >>> print(b, [_basechange_int(num, b) for num in range(11)]) 3 [[0], [1], [2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2], [1, 0, 0], [1, 0, 1]] >>> """ if num == 0: return [0] result = [] while num != 0: num, d = divmod(num, b) result.append(d) return result[::-1]
def fairshare(b=2):
for i in count(): yield sum(_basechange_int(i, b)) % b
if __name__ == '__main__':
for b in (2, 3, 5, 11): print(f"{b:>2}: {str(list(islice(fairshare(b), 25)))[1:-1]}")</lang>
- Output:
2: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 3: 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 5: 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4
Functional
<lang python>Fairshare between two and more
from itertools import count, islice from functools import reduce
- thueMorse :: Int -> [Int]
def thueMorse(base):
Thue-Morse sequence for a given base. return map(baseDigitsSumModBase(base), count(0))
- baseDigitsSumModBase :: Int -> Int -> Int
def baseDigitsSumModBase(base):
For any integer n, the sum of its digits in a given base, modulo that base. def go(n): return sum(unfoldl( lambda x: Nothing() if 0 == x else Just(divmod(x, base)) )(n)) % base return lambda n: go(n)
- TEST ----------------------------------------------------
- main :: IO ()
def main():
First 25 fairshare terms for a given number of players
print( fTable( main.__doc__ + ':\n' )(repr)( lambda xs: '[' + ','.join( [str(x).rjust(2, ' ') for x in xs] ) + ' ]' )( compose(take(25), thueMorse) )([2, 3, 5, 11]) )
- GENERIC -------------------------------------------------
- Just :: a -> Maybe a
def Just(x):
Constructor for an inhabited Maybe (option type) value. Wrapper containing the result of a computation. return {'type': 'Maybe', 'Nothing': False, 'Just': x}
- Nothing :: Maybe a
def Nothing():
Constructor for an empty Maybe (option type) value. Empty wrapper returned where a computation is not possible. return {'type': 'Maybe', 'Nothing': True}
- compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
Composition, from right to left, of a series of functions. return lambda x: reduce( lambda a, f: f(a), fs[::-1], x )
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function -> f -> xs -> tabular string. def go(xShow, fxShow, f, xs): ys = [xShow(x) for x in xs] w = max(map(len, ys)) return s + '\n' + '\n'.join(map( lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)), xs, ys )) return lambda xShow: lambda fxShow: lambda f: lambda xs: go( xShow, fxShow, f, xs )
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n, or xs itself if n > length xs. return lambda xs: ( xs[0:n] if isinstance(xs, (list, tuple)) else list(islice(xs, n)) )
- unfoldl(lambda x: Just(((x - 1), x)) if 0 != x else Nothing())(10)
- -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- unfoldl :: (b -> Maybe (b, a)) -> b -> [a]
def unfoldl(f):
Dual to reduce or foldl. Where these reduce a list to a summary value, unfoldl builds a list from a seed value. Where f returns Just(a, b), a is appended to the list, and the residual b is used as the argument for the next application of f. When f returns Nothing, the completed list is returned. def go(v): x, r = v, v xs = [] while True: mb = f(x) if mb.get('Nothing'): return xs else: x, r = mb.get('Just') xs.insert(0, r) return xs return lambda x: go(x)
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
First 25 fairshare terms for a given number of players: 2 -> [ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ] 3 -> [ 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 ] 5 -> [ 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 ] 11 -> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 0, 2, 3, 4 ]
REXX
<lang rexx>/*REXX program calculates N terms of the fairshare sequence for some group of peoples.*/ parse arg n g /*obtain optional arguments from the CL*/ if n== | n=="," then n= 25 /*Not specified? Then use the default.*/ if g= | g="," then g= 2 3 5 11 /* " " " " " " */
/* [↑] a list of a number of peoples. */ do p=1 for words(g); r= word(g, p) /*traipse through the bases specfiied. */ $= 'base' right(r, 2)': ' /*construct start of the 1─line output.*/ do j=0 for n; $= $ right( sumDigs( base(j, r)) // r, 2)',' end /*j*/ /* [↑] append # (base R) mod R──►$ list*/ say strip($, , ",") /*elide trailing comma from the $ list.*/ end /*p*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ base: parse arg #,b,,y; @= 0123456789abcdefghijklmnopqrstuvwxyz; @@= substr(@,2)
do while #>=b; y= substr(@, #//b + 1, 1)y; #= #%b; end; return substr(@, #+1, 1)y
/*──────────────────────────────────────────────────────────────────────────────────────*/ sumDigs: parse arg x; !=0; do i=1 for length(x); != !+pos(substr(x,i,1),@@); end; return !</lang>
- output when using the default inputs:
base 2: 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 base 3: 0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1 base 5: 0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3 base 11: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4
Rust
<lang rust>struct Digits {
rest: usize, base: usize,
}
impl Iterator for Digits {
type Item = usize; fn next(&mut self) -> Option<usize> { if self.rest == 0 { return None; } let (digit, rest) = (self.rest % self.base, self.rest / self.base); self.rest = rest; Some(digit) }
}
fn digits(num: usize, base: usize) -> Digits {
Digits { rest: num, base: base }
}
struct FairSharing {
participants: usize, index: usize,
}
impl Iterator for FairSharing {
type Item = usize; fn next(&mut self) -> Option<usize> { let digit_sum: usize = digits(self.index, self.participants).sum(); let selected = digit_sum % self.participants; self.index += 1; Some(selected) }
}
fn fair_sharing(participants: usize) -> FairSharing {
FairSharing { participants: participants, index: 0 }
}
fn main() {
for i in vec![2, 3, 5, 7] { println!("{}: {:?}", i, fair_sharing(i).take(25).collect::<Vec<usize>>()); }
}</lang>
- Output:
2: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0] 3: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1] 5: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3] 7: [0, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 0, 2, 3, 4, 5, 6, 0, 1, 3, 4, 5, 6]
Sidef
<lang ruby>for b in (2,3,5,11) {
say ("#{'%2d' % b}: ", 25.of { .sumdigits(b) % b })
}</lang>
- Output:
2: [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0] 3: [0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1] 5: [0, 1, 2, 3, 4, 1, 2, 3, 4, 0, 2, 3, 4, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 2, 3] 11: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 2, 3, 4]
Visual Basic .NET
<lang vbnet>Module Module1
Function Turn(base As Integer, n As Integer) As Integer Dim sum = 0 While n <> 0 Dim re = n Mod base n \= base sum += re End While Return sum Mod base End Function
Sub Fairshare(base As Integer, count As Integer) Console.Write("Base {0,2}:", base) For i = 1 To count Dim t = Turn(base, i - 1) Console.Write(" {0,2}", t) Next Console.WriteLine() End Sub
Sub TurnCount(base As Integer, count As Integer) Dim cnt(base) As Integer For i = 1 To base cnt(i - 1) = 0 Next
For i = 1 To count Dim t = Turn(base, i - 1) cnt(t) += 1 Next
Dim minTurn = Integer.MaxValue Dim maxTurn = Integer.MinValue Dim portion = 0 For i = 1 To base Dim num = cnt(i - 1) If num > 0 Then portion += 1 End If If num < minTurn Then minTurn = num End If If num > maxTurn Then maxTurn = num End If Next
Console.Write(" With {0} people: ", base) If 0 = minTurn Then Console.WriteLine("Only {0} have a turn", portion) ElseIf minTurn = maxTurn Then Console.WriteLine(minTurn) Else Console.WriteLine("{0} or {1}", minTurn, maxTurn) End If End Sub
Sub Main() Fairshare(2, 25) Fairshare(3, 25) Fairshare(5, 25) Fairshare(11, 25)
Console.WriteLine("How many times does each get a turn in 50000 iterations?") TurnCount(191, 50000) TurnCount(1377, 50000) TurnCount(49999, 50000) TurnCount(50000, 50000) TurnCount(50001, 50000) End Sub
End Module</lang>
- Output:
Base 2: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 Base 3: 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 Base 5: 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 Base 11: 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4 How many times does each get a turn in 50000 iterations? With 191 people: 261 or 262 With 1377 people: 36 or 37 With 49999 people: 1 or 2 With 50000 people: 1 With 50001 people: Only 50000 have a turn
zkl
<lang zkl>fcn fairShare(n,b){ // b<=36
n.pump(List,'wrap(n){ n.toString(b).split("").apply("toInt",b).sum(0)%b })
} foreach b in (T(2,3,5,11)){
println("%2d: %s".fmt(b,fairShare(25,b).pump(String,"%2d ".fmt)));
}</lang>
- Output:
2: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 3: 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 5: 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 11: 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 0 2 3 4
For any base > 1 <lang zkl>fcn fairShare(n,base){
sum,r := 0,0; while(n){ n,r = n.divr(base); sum+=r } sum%base
} foreach b in (T(2,3,5,11)){
println("%2d: %s".fmt(b,[0..24].pump(String,fairShare.fp1(b),"%2d ".fmt)));
}</lang>