Rosetta Code

Josephus problem

Find the survivor position in the Josephus problem for n people counting every k-th.

Edit the source, then Run. Checks start after your first Run. Ctrl/⌘ + Enter runs; Tab indents. Preview services use sample data and never contact a real service.

Sourcerosettacode/popular/josephus_problem.vibe
type RunResult = {
  classic: { elimination_order: array<int>, survivor: int },
  small: { elimination_order: array<int>, survivor: int }
}

def josephus(n: int, k: int) -> { elimination_order: array<int>, survivor: int }
  circle: array<int> = []
  i = 0
  while i < n
    circle.push(i)
    i = i + 1
  end

  order: array<int> = []
  index = 0

  while circle.length > 0
    index = (index + k - 1) % circle.length
    removed = circle.fetch(index)
    order.push(removed)

    new_circle: array<int> = []
    j = 0
    while j < circle.length
      if j != index
        new_circle.push(circle.fetch(j))
      end
      j = j + 1
    end
    circle = new_circle

    if index >= circle.length
      index = 0
    end
  end

  { survivor: order.fetch(order.length - 1), elimination_order: order }
end

def run -> RunResult
  {
    classic: josephus(41, 3),
    small: josephus(5, 2)
  }
end

Output

Click Run example to see the result.

Code checks

Run once to load the checker. Your code stays in this browser.