미로찾기

var maze = {
  'a':['b','f'],
  'b':['a','c'],
  'c':['b','d'],
  'd':['c','e'],
  'e':['d','j'],
  'f':['a','g','k'],
  'g':['f','h','l'],
  'h':['g','i'],
  'i':['h'],
  'j':['e','o'],
  'k':['f','p'],
  'l':['g','q'],
  'm':['n'],
  'n':['m','o'],
  'o':['j','n'],
  'p':['k','u'],
  'q':['l','r'],
  'r':['q','s'],
  's':['r','t'],
  't':['s','y'],
  'u':['p','v'],
  'v':['u','w'],
  'w':['v','x'],
  'x':['w'],
  'y':['t']
}

function solve_maze(g,start,end){
  var qu=[]
  var done={}

  qu.push(start)
  done[start] = 1

  while (qu){
    p = qu.shift()
    v = p[p.length-1]
    if (v == end){
      return p
    }
    g[v].forEach( x => {
      if(!(x in done)){
        qu.push(p+x)
        done[x] = 1
      }
    })
  }
  return "?"
}  

console.log(solve_maze(maze,'a','y'))

가짜동전 찾기

겉보기에는 똑같은 동전 n개가 있습니다. 이중에서 한개는 싸고 가벼운 재료로 만들어진 가짜동전입니다. 좌우 무게를 비교할수 있는 양팔 저울을 이용하여 다른 동전보다 가벼운 가짜 동전을 찾아내는 알고리즘을 만들어 보세요.

def weigh(a,b,c,d):
    fake = 29
    if a <= fake and fake <= b:
        return -1
    if c <= fake and fake <= d:
        return 1
    return 0

def find_fakecoin(left,right):
    for i range(left+1, right+1):
        result = weigh(left, left, i, i)
        if result == -1:
            return left
        elif result == 1:
            return i
    return -1

n = 100
print(find_fakecoin(0,n-1))

def weigh(a,b,c,d):
    fake = 29
    print(a,b,c,d)
    if a <= fake and fake <= b:
        return -1
    if c <= fake and fake <= d:
        return 1
    return 0

def find_fakecoin(left,right):
    if left == right:
      return left

    half = (right - left + 1)//2
    g1_left = left
    g1_right = left + half - 1
    g2_left = left + half
    g2_right = right

    result = weigh(g1_left,g1_right,g2_left,g2_right)

    if result == -1:
        return find_fakecoin(g1_left,g1_right)
    elif result == 1:
        return find_fakecoin(g2_left,g2_right)
    else:
        return right

n = 100
print(find_fakecoin(0,n-1))