Задний план

Наибольший общий делитель ( для краткости gcd ) - это удобная математическая функция, поскольку она имеет много полезных свойств. Одним из них является личность Безу : если d = gcd(a, b), то существуют целые числа xи yтакие, что d = x*a + y*b. В этой задаче ваша задача состоит в том, чтобы визуализировать это свойство с помощью простого искусства ASCII.

вход

Ваши входы два положительных целых чисел aи b, приведенные в любом приемлемом формате. Вы также можете использовать унарные входные данные (повторы одного печатного символа ASCII по вашему выбору), но вы должны быть последовательными и использовать один и тот же формат для обоих входных данных. Входные данные могут быть в любом порядке, и они могут быть равны.

Выход

Ваш вывод представляет собой строку sдлины lcm(a, b) + 1( lcm обозначает наименьшее общее кратное). Символы sпредставляют целые числа от 0до lcm(a, b). Символ s[i]является строчным, oесли iкратен aили b, и период в .противном случае. Обратите внимание, что ноль кратен каждому числу. Теперь, из - за идентичности Безу, будет по крайней мере одна пара символов oв sкоторых расстояние точно gcd(a, b). Крайняя левая такая пара должна быть заменена заглавными Os; это окончательный результат.

пример

Рассмотрим входы a = 4и b = 6. Тогда у нас gcd(a, b) = 2и lcm(a, b) = 12, значит, длина sбудет 13. Кратные aи bвыделены следующим образом:

0  1  2  3  4  5  6  7  8  9 10 11 12
o  .  .  .  o  .  o  .  o  .  .  .  o

Есть две пары os с расстоянием два, но мы заменим только самые левые с Os, поэтому окончательный результат

o...O.O.o...o

Правила и оценки

Вы можете написать полную программу или функцию. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.

Контрольные примеры

 1  1 -> OO
 2  2 -> O.O
 1  3 -> OOoo
 4  1 -> OOooo
 2  6 -> O.O.o.o
 2  3 -> o.OOo.o
10  2 -> O.O.o.o.o.o
 4  5 -> o...OO..o.o.o..oo...o
 8  6 -> o.....O.O...o...o.o.....o
12 15 -> o...........O..O........o.....o.....o........o..o...........o
19 15 -> o..............o...o..........o.......o......o...........o..o..............OO.............o....o.........o........o.....o............o.o..............o.o............o.....o........o.........o....o.............oo..............o..o...........o......o.......o..........o...o..............o

code-golf ascii-art number-theory Zgarb
источник

1

Принимая одинарный ввод, можем ли мы выбрать любой символ? (В частности, как о ., oили O.) Или же он должен быть 1? Или 0?

Мартин Эндер

1

@ MartinBüttner Это может быть любой символ, если вы последовательны и используете один и тот же формат для обоих входов.

Згарб

2

Я удивлен, что вы не использовали 3 и 5 в качестве одного из ваших тестовых случаев.

Нил

Могу ли я использовать buildin?

Akangka

@ChristianIrwan Да, все встроенные модули разрешены.

Згарб

7

Джольф, 52 байта

on*'.wm9jJΡR m*Yhm8jJDN?<*%Sj%SJ1'o'.}"'o%o"n"O%O"n

Я разделю этот код на две части.

on*'.wm9jJ
on         set n
  *'.       to a dot repeated
      m9jJ  the gcd of two numeric inputs

ΡR m*Yhm8jJDN?<*%Sj%SJ1'o'.}"'o%o"n"O%O"n
    *Y                                    multiply (repeat) Y (Y = [])
      hm8jJ                                by the lcm of two inputs + 1
  _m       DN              }              and map the array of that length
             ?<*%Sj%SJ1'o'.               "choose o if i%a*(i%b)<1; otherwise choose ."
 R                          "'            join by empty string
Ρ                            'o%o"n        replace once (capital Rho, 2 bytes): "o"+n+"o"
                                   "O%O"n   with "O"+n+"O"
                                          implicit printing

Попробуй это здесь!

Конор О'Брайен
источник

Короче всего остального пока. : P

Rɪᴋᴇʀ

1

@RikerW Да! Я надеюсь, что Джольф наконец-то победит.

Конор О'Брайен

10

Юлия, 111 110 107 103 96 байт

f(a,b)=replace(join([i%a*(i%b)<1?"o":"."for i=0:lcm(a,b)]),"o$(d="."^(gcd(a,b)-1))o","O$(d)O",1)

Это функция, которая принимает два целых числа и возвращает строку.

Ungolfed:

function f(a::Int, b::Int)
    # Construct an array of dots and o's
    x = [i % a * (i % b) < 1 ? "o" : "." for i = 0:lcm(a, b)]

    # Join it into a string
    j = join(x)

    # Replace the first pair with distance gcd(a, b) - 1
    replace(j, "o$(d = "."^(gcd(a, b) - 1))o", "O$(d)O", 1) 
end

Сохранил байт благодаря Ними!

Алекс А.
источник

10

Сетчатка , 112 109 99 94 91 байт

^
. 
+r`(?<!^\1+). (.+) 
$'$0
.(?=.* (.+) (.+))(?=\1* |\2* )
o
o(\.*)o((\1\.*o)*) .*
O$1O$2

Я думаю, что она не очень конкурентоспособна, но теория чисел в Retina всегда довольно забавная. :)

Вводит в виде одинарных чисел, используя .в качестве одинарной цифры.

Попробуйте онлайн.

объяснение

^
.

Это вставляет .и пробел перед входом. Это в конечном итоге станет выходом.

+r`(?<!^\1+). (.+) 
$'$0

Это добавляет LCM aи bк строке. Так как у нас уже .есть, мы в конечном итоге lcm(a,b)+1. Это достигается путем многократного добавления bдо тех пор, пока aне будет разделен этот новый префикс. Мы записываем aв группу один, а затем проверяем, можем ли мы достичь начала строки, сопоставляя этот захват хотя бы один раз. bзатем вставляется в строку через редко используемый, $'который вставляет все после совпадения в подстановку.

.(?=.* (.+) (.+))(?=\1* |\2* )
o

Этот соответствует символам в положениях, которые разделены aили b. Он использует тот факт, что результат является симметричным: поскольку lcm(a,b)он делится на оба aи bидет влево, вычитая экземпляры aили bвыдает тот же шаблон, что и вправо 0, добавляя их. Первый взгляд вперед просто захватывает aи b. Второе предпросмотр проверяет наличие нескольких aили каждого bсимвола перед первым пробелом.

o(\.*)o((\1\.*o)*) .*
O$1O$2

Как указано в Википедии, в дополнение к личности Безу это также верно, что

Наибольшим общим делителем dявляется наименьшее положительное целое число, которое можно записать как ax + by.

Это означает, что GCD будет соответствовать кратчайшему промежутку между двумя os на выходе. Так что нам вообще не нужно искать GCD. Вместо этого мы просто ищем первый случай кратчайшего разрыва. o(\.*)oсопоставляет пробел кандидата и фиксирует его ширину в группе 1. Затем мы пытаемся достичь первого пробела, чередуя обратную ссылку на группу 1 и os (с необязательными дополнительными .s). Если есть более короткий разрыв справа, это не будет соответствовать, потому что мы не можем преодолеть этот разрыв с помощью обратной ссылки. Как только все дальнейшие промежутки будут по крайней мере такими же широкими, как и текущий, это совпадет. Мы фиксируем конец строки LCM в группу 2 и сопоставляем остаток строки с .*. Мы пишем в верхнем регистреOs (с промежутком между ними), а также оставшуюся часть строки LCM, но отбросьте все, начиная с пробела, чтобы удалить aи bиз конечного результата.

Мартин Эндер
источник

Я не знаю много о теории чисел Retina, но не установит ли входной символ что-то, что не требует экранирования байтов? Т.е. (\.*)=>(a*)

Конор О'Брайен

@ CᴏɴᴏʀO'Bʀɪᴇɴ Да, но тогда мне придется заменить его на .более поздний, который стоит четыре байта (а избавление от побегов спасает только 3).

Мартин Эндер

Оу. Круто! Очень интересный ответ.

Конор О'Брайен

5

𝔼𝕊𝕄𝕚𝕟, 50 символов / 90 байтов

⩥Мū⁽îí+1)ⓜ$%î⅋$%í?⍘.:⍘o)⨝ċɼ(`o⦃⍘.ĘМũ⁽îí-1)}o”,↪$ú⬮

Try it here (Firefox only).

Должен быть способ играть в гольф дальше!

объяснение

Это основной двухфазный алгоритм. Это на самом деле довольно просто.

Фаза 1

⩥Мū⁽îí+1)ⓜ$%î⅋$%í?⍘.:⍘o)⨝

Сначала мы создаем диапазон от 0 до LCM + 1. Затем мы отображаем его, проверяя, является ли какой-либо из входных факторов фактором текущего элемента в диапазоне. Если это так, мы заменим этот элемент на o; в противном случае мы заменим его на .. Присоединение к ней дает нам серию точек и точек, которые мы можем перейти ко второй фазе.

Фаза 2

ċɼ(`o⦃⍘.ĘМũ⁽îí-1)}o”,↪$ú⬮

Это всего лишь одна большая функция замены. Регулярное выражение создается как o[dots]o, где количество точек определяется GCD-1. Поскольку это регулярное выражение не является глобальным, оно будет соответствовать только первому вхождению. После этого совпадение заменяется с O[dots]Oпомощью функции toUpperCase.

Mama Fun Roll
источник

3

MATL , 72 байта

Использует версию 6.0.0 , которая является более ранней, чем эта проблема. Код работает в Matlab и в Octave.

2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)

пример

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 > 
> 1
> 1
OO

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 > 
> 2
> 3
o.OOo.o

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 > 
> 12
> 15
o...........O..O........o.....o.....o........o..o...........o

объяснение

Я понятия не имею, как это работает. Я просто набрал символы случайным образом. Я думаю, что есть какая-то свертка.

Изменить: попробуйте онлайн! Код в ссылке был немного изменен, чтобы соответствовать изменениям в языке (по состоянию на 2 июня 2016 года).

Луис Мендо
источник

Вы не можете набрать 72-байтовую программу случайным образом. Вычислит вероятность позже (после сна и АКТА на некоторое время)

CalculatorFeline

2

Japt , 83 байта

'.pD=U*V/(C=(G=@Y?G$($YX%Y :X} $($UV)+1 £Y%U©Y%V?".:o"} $.replace($E=`o{'.pC-1}o`Eu

Еще не полностью в гольф ... И не хочет играть в гольф: /

nicael
источник

Вы не можете использовать rвместо $.replace($ ?

ETHproductions

@ Я не понял, как заменить без флага g, так что нет, не могу.

Никель

2

Javascript, 170 164 161 153 145 141 136 байт

(a,b)=>[...Array(a*b/(c=(g=(a,b)=>b?g(b,a%b):a)(a,b))+1)].map((x,i)=>i%a&&i%b?'.':'o').join``.replace(`o${e='.'.repeat(c-1)}o`,`O${e}O`)

Это довольно долго ....

Демо , явно определенные переменные, потому что интерпретатор использует строгий режим.

nicael
источник

Попробуйте заменить i%a<1||i%b<1?'o':'.'наi%a&&i%b?'.':'o'

Mama Fun Roll

О да, я думаю, что вы можете присоединиться к псевдониму.

Mama Fun Roll

@ ן nɟuɐɯɹɐ ן oɯ спасибо, также заменяя массивы простым повторением.

nicael

О, тогда в этом случае вы, вероятно, не должны присоединяться к псевдониму, если у вас нет 3 его случаев.

Mama Fun Roll

[...Array((d=a*b/(c=(g=(a,b)=>b?g(b,a%b):a)(a,b)))+1).keys()].map(i=>i%a&&i%b?'.':'o')экономит два байта (Я также пытался использовать индексирование строк для создания '.' И 'o', но это на самом деле стоит два байта.)

Нейл

1

Python 2, 217 200 191 байт

Это немного тупо, но это работает. Любые советы по игре в гольф приветствуются, ~~особенно если вы знаете, как решить эту s[i] = s[v] = "o"проблему, с которой я столкнулся, где это переписало бы "О"~~ Понял!

g=lambda a,b:b and g(b,a%b)or a
def f(a,b):
 h=g(a,b);x=1+a*b/h;s=["."]*x;v=k=0
 for i in range(x):
    if(i%a)*(i%b)<1:
     if k:s[i]="o"
     else:k=i==h+v;s[i]=s[v]="oO"[k]
     v=i
 return''.join(s)

Ungolfed:

def gcd(a,b):                           # recursive gcd function
    if b:
        return g(b,a%b)
    else:
        return a
def f(a,b):
    h = gcd(a,b)
    x = 1 + a*b/h                       # 1 + lcm(a,b)
    s = ["."] * x
    v = 0
    k = 0
    for i in range(x):
        if i%a == 0 and i % b == 0:
            if k == 0:
                k = (i == h+v)          # correct distance apart?
                if k:                   # if "O" just found
                    s[i] = s[v] = "O"
                else:
                    s[i] = s[v] = "o"
            else:
                s[i] = "o"              # if "O" already found, always "o"
            v = i                       # If we found an "o" or an "O", i is the new v
    return ''.join(s)

Sherlock9
источник

Визуализируйте наибольший общий делитель

Задний план

вход

Выход

пример

Правила и оценки

Контрольные примеры

Ответы:

Джольф, 52 байта

Юлия, 111 110 107 103 96 байт

Сетчатка , 112 109 99 94 91 байт

объяснение

𝔼𝕊𝕄𝕚𝕟, 50 символов / 90 байтов

объяснение

Фаза 1

Фаза 2

MATL , 72 байта

пример

объяснение

Japt , 83 байта

Javascript, 170 164 161 153 145 141 136 байт

Python 2, 217 200 191 байт