Ambiguous Roman Numeral Magic Squares

10

The king of Ancient Rome is having difficulties determining if a magic square is valid or not, because the magic square he is checking does not include any separators between the numbers. He has hired a software engineer to help him determine if a magic square is valid or not.

Input Description

Input comes in on STDIN or command line arguments. You cannot have the input pre-initialised in a variable (e.g. "this program expects the input in a variable x"). Input is in the following format:

<top>,<middle>,<bottom>

Each of <top>, <middle>, and <bottom> is a string that will only ever contain the uppercase characters I, V, and X. It will not contain spaces or any other characters. Each string represents three Roman numerals, thus resulting in a 3x3 matrix of numbers. However, these Roman numerals may (but not necessarily) be ambiguous. Allow me to illustrate this with an example. Consider the following example row of three Roman numerals, with no spaces between each number:

IVIIIIX

Because there are no spaces between the letters, there are two possibilites to the numbers here:

  • 1, 8, 9 (I VIII IX)
  • 4, 3, 9 (IV III IX)

When you consider that all three rows of the matrix can be ambigious, there is the potential for there to be many different 3x3 matrixes from a single input.

Note that sequences such as 1, 7, 1, 9 (I VII I IX) are not possible because each row will always represent three Roman numerals. Also note that the Roman numerals must be valid, so sequences such as 1, 7, 8 (I VII IIX) are also not possible.

Output Description

Output:

  • An integer A, where A is the number of unique 3x3 matrixes that can be formed from the ambigious input, and:
  • A truthy value if any of the unique 3x3 matrixes form a magic square, or:
  • A falsy value if none of the unique 3x3 matrixes form a magic square.

The truthy and falsy values must be consistent. They are seperated by a comma.

Some explanation is required on what is counted as unique. As long as a matrix does not have exactly the same numbers in exactly the same positions as a previously found matrix, it is counted as unique. This means that reflections, etc. of previously found matrixes are counted as unique.

Example Inputs and Outputs

In these examples, I use true as my truthy value and false as my falsy value.

Input: VIIIIVI,IIIVVII,IVIXII Output: 24,true (The magic triangle is 8-1-6, 3-5-7, 4-9-2.)

Input: IIIXVIII,IVIII,VIIII Output: 210,false

Extras

  • You are not allowed to use inbuilt Roman Numeral conversion functions if your chosen language has one.

absinthe

Posted 2015-03-06T23:56:03.683

Reputation: 8 359

"king of Ancient Rome" ... Emperor? – Digital Trauma – 2015-03-07T00:40:31.453

8@DigitalTrauma It's set in an alternate universe where Ancient Rome had a king, magic squares, and software engineers. Or something like that... – absinthe – 2015-03-07T00:41:58.873

Also, you should use an interpunct (·) instead of a comma (http://en.wikipedia.org/wiki/Interpunct#Latin)

– coredump – 2015-03-07T15:23:21.573

I have "24, true" for the first, but "210, false" for the second example. I'll investigate. – coredump – 2015-03-07T16:44:10.940

@coredump The reason for the difference in answers is due to a bug in my reference program I used to generate the sample inputs and outputs. I'll fix the original post in accordance. – absinthe – 2015-03-07T22:55:05.317

What is the range of roman numerals that needs to be considered? – MickyT – 2015-03-09T00:40:15.620

@MickyT All roman numerals that can be created with the characters I, V, and X. So from 1 (I) to to 39 (XXXIX). – absinthe – 2015-03-09T00:41:58.480

1@DigitalTrauma Rome had kings until about 509BC. – Jon B – 2015-03-10T02:34:55.213

Answers

4

Perl, 219 237

Line breaks added for clarity.

#!perl -p
%x=(I,1,IV,4,V,5,IX,9,X,10);
$a="(X{0,3}(?:V?I{1,3}|I?V|IX)|X{1,3})"x3;
m*^$a,$a,$a$(?{
  @z=map"$$_",0..9;
  $r|=!grep$x-$_,map{$x=eval s/./ $z[$&]/gr=~s/IX|IV|\S/+$x{$&}/gr}123,456,789,147,258,369,159,357;
  ++$-
})^*;
$_="$-,$r"

Test me.

nutki

Posted 2015-03-06T23:56:03.683

Reputation: 3 634

4

Prolog - 686

:-lib(util),lib(sd). r(S,R):-string_list(S,L),g(L,R). g(L,[N1,N2,N3]):-append(L1,X,L),append(L2,L3,X),n(L1,N1),n(L2,N2),n(L3,N3). n([73,86],4). n([73,88],9). n([73,73,73],3). n([73,73],2). n([73],1). n([86],5). n([86|N],D):-n(N,E),E<4,D is E+5. n([88|N],D):-n(N,E),D is E+10. n([88],10). m(M,[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3]):-split_string(M,",","",[X,Y,Z]),r(X,[X1,X2,X3]),r(Y,[Y1,Y2,Y3]),r(Z,[Z1,Z2,Z3]). a(L):-alldifferent(L),L=[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3],l(X1,X2,X3,T),l(Y1,Y2,Y3,T),l(Z1,Z2,Z3,T),l(X1,Y1,Z1,T),l(X2,Y2,Z2,T),l(X3,Y3,Z3,T). l(A,B,C,T):-T is A+B+C. p:-read_line(S),findall(L,m(S,L),A),length(A,C),findall(L,(member(L,A),a(L)),B),(B=[_|_]->R=true;R=false),writeln((C,R)).

Ungolfed

% I : 73
% V : 86
% X : 88
:-lib(util).
:-lib(sd).
r(S,R) :- string_list(S,L), g(L,R).
g(L,[N1,N2,N3]):-
    append(L1,X,L),
    append(L2,L3,X),
    n(L1,N1),n(L2,N2),n(L3,N3).
n([73,86],4).
n([73,88],9).
n([73,73,73],3).
n([73,73],2).
n([73],1).
n([86],5).
n([86|N],D):-n(N,E),E<4,D is E+5.
n([88|N],D):-n(N,E), D is E+10.
n([88],10).
m(M,[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3]) :-
    split_string(M,",","",[X,Y,Z]),
    r(X,[X1,X2,X3]),
    r(Y,[Y1,Y2,Y3]),
    r(Z,[Z1,Z2,Z3]).
a(L) :-
    alldifferent(L),
    L=[X1,X2,X3,Y1,Y2,Y3,Z1,Z2,Z3],
    l(X1,X2,X3,T),
    l(Y1,Y2,Y3,T),
    l(Z1,Z2,Z3,T),
    l(X1,Y1,Z1,T),
    l(X2,Y2,Z2,T),
    l(X3,Y3,Z3,T).
l(A,B,C,T):-T is A+B+C.
p :- read_line(S),
     findall(L,m(S,L),A),
     length(A,C),
     findall(L,(member(L,A),a(L)),B),
     (B=[_|_]->R=true;R=false),
     writeln((C,R)).

Of course, p could also be defined as:

p :- read_line(S),
     findall(L,m(S,L),A),
     length(A,C),
     findall(L,(member(L,A),a(L)),B),
     writeln(C),
     B=[_|_].

In that case, the environment would say 'Yes' or 'No' after writing the number of squares.

Example

Using eclipse.

[eclipse 105]: p.
 VIIIIVI,IIIVVII,IVIXII
24, true

[eclipse 106]: p.
 IIIXVIII,IVIII,VIIII
210, false

Example results for the second one are pasted here.

coredump

Posted 2015-03-06T23:56:03.683

Reputation: 6 292

2

Python, 442 chars

R=range
L=len
S=sum
N={}
for i in R(40):
 r="";j=i
 while j>9:r+="X";j-=10
 if j>8:r+="IX";j-=9
 if j>4:r+="V";j-=5
 if j>3:r+="IV";j-=4
 N[r+"III"[:j]]=i
a,b,c=map(lambda x:sum([[Z]*all(Z)for i in R(L(x))for j in R(L(x))for Z in[map(N.get,(x[:i],x[i:j],x[j:]))]],[]),raw_input().split(","))
print L(a)*L(b)*L(c),any(S(x)==S(y)==S(z)==S(q[::3])==S(q[1::3])==S(q[2::3])==S(q[::4])==S(q[2:-1:2])for x in a for y in b for z in c for q in[x+y+z])

The code first builds N which is a mapping from roman numeral string to its value for all possible numbers we might need. Splits each line into three in every possible way and checks which of the resulting triples all have mappings in N. The final any sees if any combination is a magic square.

Keith Randall

Posted 2015-03-06T23:56:03.683

Reputation: 19 865

2

Haskell, 451 429 423 bytes

import Data.List
(#)=splitAt
(%)=map
w=length
r"X"=10
r('X':a)=10+r a
r a=case elemIndex a["I","II","III","IV","V","VI","VII","VIII","IX"]of Just i->i+1;_->0
s l=[r%[a,b,c]|x<-[2..w l],y<-[1..x],let(d,c)=x#l;(a,b)=y#d,r a*r b*r c>0]
e[a,b,c]=a==b&&a==c
p[l,m,n]=[1|a<-l,b<-m,c<-n,e$sum%[a,b,c],e$sum%(transpose[a,b,c])]
f i=(show$product$w%(s%i))++","++(show$0<(w$p$s%i))
q ','='\n'
q a=a
i=getLine>>=putStrLn.f.lines.map q

Usage:

*Main> i                           -- repl prompt, call i
VIIIIVI,IIIVVII,IVIXII             -- input via STDIN    
24,True                            -- output
*Main> i
IIIXVIII,IVIII,VIIII
210,False

About 70 bytes just to get the input and output format right.

The function r converts a roman number (given as a string) to an integer (if it's not a valid roman number 0 is returned). s splits a string of roman digits into 3 substring and keeps those triples with valid roman numbers and converts them via r to integers . e checks if all integers of a three element list are equal. p takes three strings of roman digits, splits them via s into lists of integers, combines one integer of each list to triples and keeps those with equal sums in all directions. f calculates the number of valid matrices and checks if p returns the empty list (no valid solution) or not (valid solution exists). The main function i reads the input from STDIN, converts it to a list of strings (q helps by replacing , with \n) and calls p.

nimi

Posted 2015-03-06T23:56:03.683

Reputation: 34 639

1

R, 489 474 464

This got a lot bigger than I wanted, but I suspect I can golf it down a bit.

It uses a brute force method, by calculating all the possible Roman Numeral combinations and their corresponding digits.

Once that is done it compares the input to the Roman Numeral list and gets the possible digits.

From there it goes through each matrix of numbers and test for the magic square, finally outputting the result.

s=strsplit;e=expand.grid;P=paste0;d=do.call;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[n];p=d(P,e(r,r,r));n=d(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=F;N=nrow(C);for(n in 1:N){T=matrix(strtoi(unlist(C[n,])),nr=3);E=E||length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1};P(N,',',any(E))

Test Run. It waits for input once pasted into the RGui.

> e=expand.grid;l=length;s=strsplit;P=paste0;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[-40];p=do.call(P,e(r,r,r));n=do.call(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=c();N=nrow(C);for(n in 1:N){T=matrix(as.integer(unlist(C[n,])),nr=3);E=c(E,length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1)};paste(N,',',any(E))
VIIIIVI,IIIVVII,IVIXII
[1] "24 , TRUE"
> e=expand.grid;l=length;s=strsplit;P=paste0;i=readline();i=s(i,',');n=1:39;r=c(t(outer(c('','X','XX','XXX'),c('I','II','III','IV','V','VI','VII','VIII','IX','X'),P)))[-40];p=do.call(P,e(r,r,r));n=do.call(paste,e(n,n,n));m=lapply(i[[1]],function(x)which(p==x));C=e(s(n[m[[1]]],' '),s(n[m[[2]]],' '),s(n[m[[3]]],' '));E=c();N=nrow(C);for(n in 1:N){T=matrix(as.integer(unlist(C[n,])),nr=3);E=c(E,length(unique(c(rowSums(T),colSums(T),sum(diag(T)),sum(diag(T[3:1,])))))==1)};paste(N,',',any(E))
IIIXVIII,IVIII,VIIII
[1] "210 , FALSE"
>

MickyT

Posted 2015-03-06T23:56:03.683

Reputation: 11 735