Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

Return to Answer

replaced http://codegolf.stackexchange.com/ with https://codegolf.stackexchange.com/
Source Link

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.

(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)

A version of the algorithm at the end of my Python answer my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q
 -- ceiling throws a type-related fit with ceiling(z*k/(k-1))
 -- better to use - div (-z * k) (k - 1)
 | m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q) 

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.

(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)

A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q
 -- ceiling throws a type-related fit with ceiling(z*k/(k-1))
 -- better to use - div (-z * k) (k - 1)
 | m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q) 

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.

(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)

A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q
 -- ceiling throws a type-related fit with ceiling(z*k/(k-1))
 -- better to use - div (-z * k) (k - 1)
 | m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q) 
More golfing
Source Link
Sherlock9
  • 12.4k
  • 1
  • 31
  • 68

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.

(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x
(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)

A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 8262 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
 -- ceiling throws a type-related fit with ceiling(x*m/(m-1))
 -- better to use - div (-x * m) (m - 1)
 | val <= step' = by_step (-div (val * step') (1 - step')) limit step'
 | otherwise = val
jos_gkp num step q
 -- ceiling throws a type-related fit with ceiling(z*k/(k-1))
 -- better to use - div (-z * k) (k - 1)
 | m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q) 

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.

(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x

A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 82 bytes, and has not been golfed down as much as the first, it is faster for large n and small k

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
 -- ceiling throws a type-related fit with ceiling(x*m/(m-1))
 -- better to use - div (-x * m) (m - 1)
 | val <= step' = by_step (-div (val * step') (1 - step')) limit step'
 | otherwise = val

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.

(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)

A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q
 -- ceiling throws a type-related fit with ceiling(z*k/(k-1))
 -- better to use - div (-z * k) (k - 1)
 | m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q) 
Adding an explanation
Source Link
Sherlock9
  • 12.4k
  • 1
  • 31
  • 68

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.

(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x

A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 82 bytes, and has not been golfed down as much as the first, it is faster for large n and small k

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
 -- ceiling throws a type-related fit with ceiling(x*m/(m-1))
 -- better to use - div (-x * m) (m - 1)
 | val <= step' = by_step (-div (val * step') (1 - step')) limit step'
 | otherwise = val

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.

Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.

Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.

(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x

A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 82 bytes, and has not been golfed down as much as the first, it is faster for large n and small k

Ungolfed:

First algorithm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Second algorithm

jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
 -- ceiling throws a type-related fit with ceiling(x*m/(m-1))
 -- better to use - div (-x * m) (m - 1)
 | val <= step' = by_step (-div (val * step') (1 - step')) limit step'
 | otherwise = val
More golfing
Source Link
Sherlock9
  • 12.4k
  • 1
  • 31
  • 68
Loading
More golfing
Source Link
Sherlock9
  • 12.4k
  • 1
  • 31
  • 68
Loading
Source Link
Sherlock9
  • 12.4k
  • 1
  • 31
  • 68
Loading

AltStyle によって変換されたページ (->オリジナル) /