# josVis.py
# input: 8 2  or  40 7
# info: https://en.wikipedia.org/wiki/Josephus_problem

'''
n denotes the number of people in the initial circle, 
and k is the count for each step, that is, k-1 people 
are skipped and the k-th is executed. 

The people in the circle are numbered from 1 to n, 
the starting position being 1 and the counting being 
inclusive. 
'''

import math, random, sys
import os
os.environ['PYGAME_HIDE_SUPPORT_PROMPT'] = "hide"
import pygame
from pygame.locals import *

# some colors
BLACK = (   0,   0,   0)
WHITE = ( 255, 255, 255)
RED   = ( 255,   0,   0)
LGRAY = ( 230, 228, 255)
DGRAY = ( 120, 119, 116)

MARKER_RADIUS = 12
GAP = 3
MAX_REMOVE = 5  # max IDs to remove per call
                # to removeMarkers()


def setLocs(n):
  locs = []
  xc, yc = scrWidth/2, scrHeight/2
  angleIncr = 360/n
  angle = 0
  for i in range(n):
    ang = math.radians(angle)
    x = xc + radius*math.cos(ang)
    y = yc - radius*math.sin(ang)
    locs.append((x,y))
    angle += angleIncr
  return locs


def removeMarkers(idx):
  # remove at most MAX_REMOVE IDs starting
  # from index idx, and return final index position
  numRemove = MAX_REMOVE
  numPresent = sum(isPresent)
  if numPresent == 1:
    print("Only ID", (idx+1), "left")
    return idx
  elif numPresent <= MAX_REMOVE:
    numRemove = numPresent-1

  print("Removed:", end = ' ')
  for j in range(numRemove):
    idx = findNextStep(idx, k)
    print((idx+1), end = ' ')
    isPresent[idx] = False
    removed.append(idx)
    idx = findNext(idx)
  print()

  print("At ID", (idx+1))
  return idx


def findNextStep(i, k):
  # return index which is k steps after index i
  # when only a isPresent ID is counted as a step
  count = 1
  while (count < k):
     i = (i+1)%len(isPresent)
     if isPresent[i]:
       count += 1
  return i


def findNext(idx):
  # return index of next isPresent ID,
  # starting from idx
  while not isPresent[idx]:
    idx = (idx+1)%len(isPresent)
  return idx
       

def drawMarker(screen, loc, color, tcolor, numStr):
    pygame.draw.circle(screen, color, loc, MARKER_RADIUS)
    label = font.render(numStr, True, tcolor)
    screen.blit(label, label.get_rect(center = loc))


def drawArrow(screen, loc):
  x = loc[0]-(MARKER_RADIUS*3); y = loc[1]
  pygame.draw.polygon(screen, BLACK, 
       ((x, y-5), (x, y+5), 
        (x+10, y+5), (x+10, y+15), 
        (x+20, y), (x+10, y-15), (x+10, y-5)) )


# ---------- main -------------

n, k = map(int, input("n k=? ").split())

pygame.init()
screen = pygame.display.set_mode([600, 600])
screen.fill(WHITE)
pygame.display.set_caption("Circles")
clock = pygame.time.Clock()

scrWidth, scrHeight = screen.get_size()

radius = round(n*(2*MARKER_RADIUS + GAP)/(2*math.pi))
# print("Required radius:", radius)

if (radius >= scrWidth/2) or (radius >= scrHeight/2):
  print("Too many IDs for window size")
  pygame.quit()
  sys.exit()

font = pygame.font.SysFont("Arial", 12)  # for ID no.
msgFont = pygame.font.SysFont("Arial", 20)

locs = setLocs(n)
isPresent = [True]*n
removed = []
idx = 0
print("Starting at ID", (idx+1))

running = True
isPaused = True
while running:
  clock.tick(30)

  for event in pygame.event.get():
    if event.type == QUIT:
      running = False
    if (event.type == KEYDOWN):
      if (event.key == K_ESCAPE):
        running = False
      elif (event.key == K_n):   # press n
        isPaused = False

  # update
  if not isPaused:
    removed = []
    idx = removeMarkers(idx)
    isPaused = True

  # draw
  screen.fill(WHITE)
  for i in range(len(locs)):
    if isPresent[i]:
      drawMarker(screen, locs[i], LGRAY, BLACK, str(i+1))
    elif i in removed:   # just killed
      drawMarker(screen, locs[i], DGRAY, WHITE, str(i+1))
    else:   # long dead
      drawMarker(screen, locs[i], BLACK, WHITE, str(i+1))

  drawArrow(screen, locs[idx])

  screen.blit( msgFont.render("Press 'n' to continue", 
                      True, BLACK), 
                      [scrWidth-180, scrHeight-40])

  pygame.display.update()

pygame.quit()