28
\$\begingroup\$

Background

The greatest common divisor (gcd for short) is a convenient mathematical function, since it has many useful properties. One of them is Bézout's identity: if d = gcd(a, b), then there exist integers x and y such that d = x*a + y*b. In this challenge, your task is to visualize this property with simple ASCII art.

Input

Your inputs are two positive integers a and b, given in any reasonable format. You may also take unary inputs (repetitions of a single printable ASCII character of your choice), but you must be consistent and use the same format for both inputs. The inputs may be in any order, and they may be equal.

Output

Your output is a string s of length lcm(a, b) + 1 (lcm stands for lowest common multiple). The characters of s represent integers from 0 to lcm(a, b). The character s[i] is a lowercase o if i is a multiple of a or b, and a period . otherwise. Note that zero is a multiple of every number. Now, because of Bézout's identity, there will be at least one pair of characters o in s whose distance is exactly gcd(a, b). The leftmost such pair is to be replaced by uppercase Os; this is the final output.

Example

Consider the inputs a = 4 and b = 6. Then we have gcd(a, b) = 2 and lcm(a, b) = 12, so the length of s will be 13. The multiples of a and b are highlighted as follows:

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

There are two pairs of os with distance two, but we will only replace the leftmost ones with Os, so the final output is

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

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

 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
\$\endgroup\$
  • 1
    \$\begingroup\$ When taking unary input, can we choose any character? (In particular, how about ., o or O.) Or does it have to be 1? Or 0? \$\endgroup\$ – Martin Ender Jan 1 '16 at 19:38
  • 1
    \$\begingroup\$ @MartinBüttner It can be any character, as long as you're consistent and use the same format for both inputs. \$\endgroup\$ – Zgarb Jan 1 '16 at 19:39
  • 2
    \$\begingroup\$ I'm surprised you didn't use 3 and 5 as one of your test cases. \$\endgroup\$ – Neil Jan 1 '16 at 22:27
  • \$\begingroup\$ Can I use buildin? \$\endgroup\$ – Akangka Jan 2 '16 at 10:06
  • \$\begingroup\$ @ChristianIrwan Yes, all built-ins are allowed. \$\endgroup\$ – Zgarb Jan 2 '16 at 14:05
7
\$\begingroup\$

Jolf, 52 bytes

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

I will split this code up into two parts.

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

Try it here!

\$\endgroup\$
  • \$\begingroup\$ Shorter than everything else so far. :P \$\endgroup\$ – Rɪᴋᴇʀ Jan 1 '16 at 21:55
  • 1
    \$\begingroup\$ @RikerW Yes! I'm hoping Jolf will finally win, once. \$\endgroup\$ – Conor O'Brien Jan 1 '16 at 21:58
10
\$\begingroup\$

Julia, 111 110 107 103 96 bytes

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)

This is a function that accepts two integers and returns a string.

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

Saved a byte thanks to nimi!

\$\endgroup\$
10
\$\begingroup\$

Retina, 112 109 99 94 91 bytes

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

Not very competitive, I think, but number theory in Retina is always quite fun. :)

Takes input as unary numbers using . as the unary digit.

Try it online.

Explanation

^
. 

This inserts a . and a space in front of the input. This will ultimately become the output.

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

This prepends the LCM of a and b to the string. Since we already have a . there, we'll end up with lcm(a,b)+1. This is accomplished by repeatedly prepending b as long as a does not divide this new prefix. We capture a into a group one and then check if we can reach the beginning of the string by matching that capture at least once. b is then inserted into the string via the rarely used $' which inserts everything after the match into the substitution.

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

This one matches characters at positions which are divided by a or b. It makes use of the fact that the result is symmetric: since lcm(a,b) is divided by both a and b going left by subtracting instances of a or b yields the same pattern as going right from 0 by adding them. The first lookahead simply captures a and b. The second lookahead checks that there is a multiple of each a or b characters before the first space.

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

As stated on Wikipedia, in addition to Bézout's identity it is also true that

The greatest common divisor d is the smallest positive integer that can be written as ax + by.

This implies that the GCD will correspond to the shortest gap between two os in the output. So we don't have to bother finding the GCD at all. Instead we just look for first instance of the shortest gap. o(\.*)o matches a candidate gap and captures its width into group 1. Then we try to reach the first space by alternating between a backreference to group 1 and os (with optional additional .s). If there is a shorter gap further to the right, this will fail to match, because we cannot get past that gap with the backreference. As soon as all further gaps are at least as wide as the current one, this matches. We capture the end of the LCM-string into group 2 and match the remainder of the string with .*. We write back the uppercase Os (with the gap in between) as well as the remainder of the LCM string, but discard everything starting from the space, to remove a and b from final result.

\$\endgroup\$
  • \$\begingroup\$ I don't know much about Retina number theory, but wouldn't setting the input character to something that does not require escaping save bytes? I.e. (\.*) => (a*) \$\endgroup\$ – Conor O'Brien Jan 1 '16 at 22:07
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Yes, but then I'd have to replace it with . later, which costs four bytes (and getting rid of the escapes only saves 3). \$\endgroup\$ – Martin Ender Jan 1 '16 at 22:10
  • \$\begingroup\$ Ohh. Cool! Very interesting answer. \$\endgroup\$ – Conor O'Brien Jan 1 '16 at 22:13
5
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 50 chars / 90 bytes

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

Try it here (Firefox only).

There must be a way to golf this further!

Explanation

This is a basic two-phase algorithm. It's actually quite simple.

Phase 1

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

First, we create a range from 0 to the LCM+1. Then we map over it, checking if either of the inputs is a factor of the current item in the range. If so, we replace that item with an o; otherwise, we replace it with a . . Joining it gives us a series of o's and dots that we can pass to phase two.

Phase 2

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

This is just one big replace function. A regex is created as o[dots]o, where the amount of dots is determined by the GCD-1. Since this regex is not global, it will only match the first occurrence. After, the match is replaced by O[dots]O using a toUpperCase function.

\$\endgroup\$
3
\$\begingroup\$

MATL, 72 bytes

Uses version 6.0.0, which is earlier than this challenge. The code runs in Matlab and in Octave.

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

Example

>> 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

Explanation

I have no idea how it works. I just typed characters randomly. I think there is some convolution involved.

Edit: Try it online! The code in the link has been slightly modified to conform to changes in the language (as of June 2, 2016).

\$\endgroup\$
  • \$\begingroup\$ You can't type a 72 byte program randomly. Will calculate probability later (after sleeping and ACTing for a while) \$\endgroup\$ – CalculatorFeline Apr 9 '16 at 4:38
2
\$\begingroup\$

Japt, 83 bytes

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

Not fully golfed yet... And doesn't want to be golfed :/

\$\endgroup\$
  • \$\begingroup\$ Can you not use r in place of $.replace($? \$\endgroup\$ – ETHproductions Jan 4 '16 at 2:53
  • \$\begingroup\$ @Eth I haven't figured out how to replace without g flag, so no, I can't. \$\endgroup\$ – nicael Jan 4 '16 at 8:29
2
\$\begingroup\$

Javascript, 170 164 161 153 145 141 136 bytes

(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`)

That's quite lonnnggggg....

Demo, explicitly defined variables because the interpreter uses strict mode.

\$\endgroup\$
  • \$\begingroup\$ Try replacing i%a<1||i%b<1?'o':'.' with i%a&&i%b?'.':'o' \$\endgroup\$ – Mama Fun Roll Jan 1 '16 at 20:36
  • \$\begingroup\$ Oh yeah, I think you can alias join. \$\endgroup\$ – Mama Fun Roll Jan 1 '16 at 20:37
  • \$\begingroup\$ @ןnɟuɐɯɹɐןoɯ thanks, also replacing arrays with simple repeat. \$\endgroup\$ – nicael Jan 1 '16 at 20:37
  • \$\begingroup\$ Oh, then in that case, you probably shouldn't alias join unless you have 3 occurrences of it. \$\endgroup\$ – Mama Fun Roll Jan 1 '16 at 20:38
  • \$\begingroup\$ [...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') saves you two bytes. (I also tried to use string indexing to create the '.' and 'o' but that actually costs two bytes.) \$\endgroup\$ – Neil Jan 1 '16 at 22:22
1
\$\begingroup\$

Python 2, 217 200 191 bytes

This is a little blunt, but it works. Any golfing tips are appreciated, especially if you know how to fix that s[i] = s[v] = "o" problem I encountered, where that would overwrite "O"s Got it!

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.