Google foobar gearing_up_for_destruction

Question

Tôi đã thử thách google foobar nhưng đã hết thời gian trong thử thách sau đây, tôi đang cố gắng xem tôi đã làm gì sai.

Challenge

Là trợ lý cá nhân Commander Lambda, bạn đã được giao nhiệm vụ cấu hình bánh răng định hướng trục của ngày tận thế của thiết bị LAMBCHOP. Nó sẽ khá đơn giản - chỉ cần thêm các bánh răng để tạo tỷ lệ xoay thích hợp. Nhưng vấn đề là, do cách bố trí của LAMBCHOP và hệ thống dầm và ống phức tạp hỗ trợ nó, các chốt sẽ hỗ trợ các bánh răng được cố định tại chỗ.

Kỹ sư của LAMBCHOP đã cung cấp cho bạn danh sách xác định vị trí của các nhóm chốt dọc theo các dầm hỗ trợ khác nhau. Bạn cần phải đặt một bánh răng trên mỗi chốt (nếu không các bánh răng sẽ va chạm với chốt không có). Các kỹ sư có rất nhiều bánh răng ở tất cả các kích cỡ khác nhau được lưu trữ, vì vậy bạn có thể chọn các bánh răng có kích thước bất kỳ, từ bán kính 1 trở lên. Mục tiêu của bạn là xây dựng một hệ thống mà bánh răng cuối cùng quay với tốc độ gấp đôi (trong vòng quay mỗi phút hoặc vòng/phút) của bánh răng đầu tiên, bất kể hướng nào. Mỗi bánh răng (ngoại trừ lần cuối) chạm và xoay bánh răng trên chốt tiếp theo ở bên phải. Cho một danh sách các số nguyên dương khác biệt có tên là chốt đại diện cho vị trí của mỗi chốt dọc theo dầm hỗ trợ, viết câu trả lời hàm (pegs), nếu có giải pháp, trả về danh sách hai số nguyên dương a và b đại diện tử số và mẫu số của bán kính bánh răng đầu tiên ở dạng đơn giản nhất của nó để đạt được mục tiêu trên, chẳng hạn bán kính = a/b. Tỷ lệ a/b phải lớn hơn hoặc bằng 1. Không phải tất cả cấu hình hỗ trợ nhất thiết sẽ có khả năng tạo tỷ lệ xoay thích hợp, vì vậy nếu nhiệm vụ là không thể, câu trả lời hàm (chốt) sẽ trả về danh sách [-1, -1]. Ví dụ, nếu các chốt được đặt tại [4, 30, 50], thì bánh răng đầu tiên có thể có bán kính là 12, bánh răng thứ hai có bán kính là 14 và bán kính cuối cùng là bán kính là 6. Do đó, thiết bị cuối cùng sẽ quay nhanh gấp hai lần cái đầu tiên. Trong trường hợp này, các chốt sẽ là [4, 30, 50] và câu trả lời (chốt) sẽ trả về [12, 1].

Các chốt danh sách sẽ được sắp xếp theo thứ tự tăng dần và sẽ chứa ít nhất 2 và không quá 20 số nguyên dương riêng biệt, tất cả nằm trong khoảng từ 1 đến 10000.

trường hợp thử nghiệm

Inputs: 
(int list) pegs = [4, 30, 50] 
Output: 
(int list) [12, 1] 

Inputs: 
(int list) pegs = [4, 17, 50] 
Output: 
(int list) [-1, -1] 

giải pháp hiện tại của tôi là như sau

def answer(pegs): 
    n = len(pegs) 
    g = range(n) 
    k = pegs[1] - pegs[0] 
    for i in range(0,k,2): 
     g[0] = i 
     for j in range(1,n): 
      g[j] = (pegs[j] - pegs[j-1]) - g[j-1] 
     if any(b < 1 for b in g): 
      continue 
     if 1.0*g[0]/g[-1] == 2.0: 
      return [g[0],1] 
    return [-1, -1] 

tôi chỉ có thể nhận được 6 trường hợp thử nghiệm để vượt qua bây giờ tôi đã chạy ra khỏi thời gian nhưng tôi tò mò giải pháp phù hợp là gì

Answer 1

Dưới đây là đoạn code làm việc trong python 2.7 mà tất cả các trường hợp thử nghiệm được thông qua bởi Google. Đây là giải pháp tốt nhất mà tôi đã đưa ra sau khi gãi giấy tờ trong một thời gian:

from fractions import Fraction 
def answer(pegs): 
    arrLength = len(pegs) 
    if ((not pegs) or arrLength == 1): 
     return [-1,-1] 

    even = True if (arrLength % 2 == 0) else False 
    sum = (- pegs[0] + pegs[arrLength - 1]) if even else (- pegs[0] - pegs[arrLength -1]) 

    if (arrLength > 2): 
     for index in xrange(1, arrLength-1): 
      sum += 2 * (-1)**(index+1) * pegs[index] 

    FirstGearRadius = Fraction(2 * (float(sum)/3 if even else sum)).limit_denominator() 
    #now that we have the radius of the first gear, we should again check the input array of pegs to verify that 
    #the pegs radius' is atleast 1. 

    currentRadius = FirstGearRadius 
    for index in xrange(0, arrLength-2): 
     CenterDistance = pegs[index+1] - pegs[index] 
     NextRadius = CenterDistance - currentRadius 
     if (currentRadius < 1 or NextRadius < 1): 
      return [-1,-1] 
     else: 
      currentRadius = NextRadius 

    return [FirstGearRadius.numerator, FirstGearRadius.denominator] 

Xem hình ảnh này cho làm thế nào tôi đã đưa ra với mã này:

Answer 2

Tôi nghĩ giải pháp của bạn nằm dọc theo dòng bên phải s, nhưng không cho phép bán kính phân đoạn.

Lưu ý rằng chúng tôi có thể xem xét thuật toán của bạn một cách biểu tượng, thiết lập g[0]=x và sau đó tính toán tất cả các giá trị g[j] theo điều khoản của x. Nó chỉ ra rằng mỗi g[j] là một hàm tuyến tính của x (với độ dốc 1 hoặc -1).

Do đó, bạn sẽ thấy rằng g[-1] = a+mx trong đó m là +1 hoặc -1 và a là một số nguyên.

Đối với một giải pháp để tồn tại bạn cần phải giải quyết các phương trình:

g[0]/g[-1] = 2 
x/(a+mx) = 2 
x=2(a+mx) 
x(1-2m)=2a 
x=2a/(1-2m) 

vì vậy đây đưa ra một giá trị ứng cử viên của x (như là một phần) mà sau đó bạn có thể kiểm tra lại để đảm bảo rằng không có bán kính trung gian đi tiêu cực .

Answer 3

Nếu bạn quan tâm đến một giải pháp làm việc hoàn hảo, đây là những gì tôi đã viết: https://gist.github.com/1lann/be45311db1bd8cbbe6650b0a3e9d1977

Nó xây dựng một hệ phương trình mà nó quyết định giá trị cho tất cả các bán kính của mỗi thiết bị. Đây là cách nó tính toán giải pháp cho 4 chốt ví dụ.

Các hệ phương trình sẽ là:

2x + a = peg[1] - peg[0] 
a + b = peg[2] - peg[1] 
b + x = peg[3] - peg[2] 

chương trình của tôi xây dựng một ma trận đại diện này:

[ 
    [2, 1, 0], 
    [0, 1, 1], 
    [1, 0, 1] 
] 

Sau đó nó tính nghịch đảo của ma trận, và sau đó áp dụng nó vào khoảng cách giữa các chốt để tìm bán kính của mọi bánh răng. Nếu bạn tự hỏi cách toán học hoạt động như thế nào, bạn có thể xem: https://www.mathsisfun.com/algebra/systems-linear-equations-matrices.html

Mỗi bánh răng sau đó được xác minh có bán kính> = 1 và cuối cùng giá trị của x * 2 được trả về. Để hỗ trợ phân số (bất kỳ số hợp lý nào), tất cả các số đều thuộc loại Phân số.

tôi đã cứng mã một số trường hợp cạnh, chẳng hạn như khi số lượng chốt = 2.

Answer 4

from fractions import Fraction 

def answer(a): 
  l = len(a) 
  if(not a or l == 1): return [-1,-1] 
  s = (a[l-1] - a[0]) if (l % 2 == 0) else (-a[l-1]-a[0]); 
  if(l > 2): 
      for i in range(1, l-1): s+= 2 * (-1)**(i+1) * a[i] 
  v = Fraction(2*(float(s)/3 if (l%2==0) else float(s))).limit_denominator(); 
  c = v; 
  for i in range(0, l-2): 
    d = a[i+1] - a[i] 
    n = d - c 
    if(c < 1 or n < 1): return [-1,-1] 
    else: c = n 
  return [v.numerator, v.denominator];