| Bytes | Lang | Time | Link |
|---|---|---|---|
| 966 | Python3 | 240809T184817Z | Ajax1234 |
| 404 | C | 160709T075604Z | Norg74 |
| 559 | Lua | 160707T143038Z | Katenkyo |
| 313 | Octave | 160701T102116Z | Sanchise |
| 754 | Befunge | 160707T145543Z | Maliafo |
| 495 | Rust | 160707T174310Z | raggy |
| 266 | Ruby | 160707T185927Z | Value In |
Python3, 966 bytes
Runs input puzzle matrix through a series of transformation convolutions.
R=range
v=lambda d:not d%2 and d%3
def C(B,x,X,y,Y):
d={}
for j in B[x:X]:
for t in j[y:Y]:d[t]=d.get(t,0)+1
return d
def f(b):
B=[b,b+[[0]*len(b[0])]][len(b)%2]
for x in R(0,len(B),2):
for y in R(0,len(B[0]),2):
d,V=C(B,x,x+2,y,y+2),-1
if len(d)==3:V=max(d,key=lambda x:d[x])
elif len(d)==2:V=[*{0,1,2}-{*d}][0]if len({*d.values()})==1 else min(d,key=lambda x:d[x])
if V>-1:
for X in R(x,x+2):
for Y in R(y,y+2):B[X][Y]=V
e=[]
for x in R(len(B)):
for y in R(len(B[0])):
for X in R(x+1,len(B)+1):
for Y in R(y+1,len(B[0])+1):
if v(A:=X-x)and v(U:=Y-y):e+=[(x,X,y,Y,A*U)]
q,s=[B],[B]
for B in q:
if len({i for k in B for i in k})==1:return B
O=[]
for I in e:
if len(d:=C(B,*I[:-1]))==2 and len({*d.values()})==1:O+=[([*{0,1,2}-{*d}][0],*I)]
for V,x,X,y,Y,_ in sorted(O,key=lambda x:x[-1],reverse=1):
T=eval(str(B))
for j in R(x,X):
for k in R(y,Y):T[j][k]=V
if T not in s:q+=[T];s+=[T];break
Python3, 1271 bytes
An even longer solution. Here, the original convolution rules have been extended to any j x k window, where j <= n and k <= m. This greatly increases performance, however, it still requires O(n^4) to produce the windows in the first place.
import math
R=range
v=lambda d:not d%2 and d%3
def C(B,x,X,y,Y):
d={}
for j in B[x:X]:
for t in j[y:Y]:d[t]=d.get(t,0)+1
return d
def f(b):
B=[b,b+[[0]*len(b[0])]][len(b)%2]
for x in R(0,len(B),2):
for y in R(0,len(B[0]),2):
d,V=C(B,x,x+2,y,y+2),-1
if len(d)==3:V=max(d,key=lambda x:d[x])
elif len(d)==2:V=[*{0,1,2}-{*d}][0]if len({*d.values()})==1 else min(d,key=lambda x:d[x])
if V>-1:
for X in R(x,x+2):
for Y in R(y,y+2):B[X][Y]=V
e=[]
for x in R(len(B)):
for y in R(len(B[0])):
for X in R(x+1,len(B)+1):
for Y in R(y+1,len(B[0])+1):
if v(A:=X-x)and v(U:=Y-y):e+=[(x,X,y,Y,A*U)]
q,s=[B],[B]
for B in q:
if len({i for k in B for i in k})==1:return B
O=[]
for I in e:
if len(d:=C(B,*I[:-1]))>1:
G=math.gcd(*d.values());M={i:d[i]/G for i in d}
if all(M[i]==int(M[i])for i in M):
M={i:int(M[i])for i in M}
if len(M)==2:
if len(o:={*M.values()})==1:O+=[([*{0,1,2}-{*M}][0],*I)]
if{1,3}==o:O+=[(min(M,key=lambda x:M[x]),*I)]
elif len(M)==3:
if[1,1,2]==sorted(M.values()):O+=[(max(M,key=lambda x:M[x]),*I)]
for V,x,X,y,Y,_ in sorted(O,key=lambda x:x[-1],reverse=1):
T=eval(str(B))
for j in R(x,X):
for k in R(y,Y):T[j][k]=V
if T not in s:q+=[T];s+=[T];break
C, 404 bytes
My first code golf, I'm pretty happy with how it turned out. Took way too long, though. It's not fully standard C, just whatever will compile under gcc with no special flags (and ignoring warnings). So there's a nested function in there. The function f takes the dimensions m and n as its first arguments, and as it's third argument takes takes an (int pointer) to an array of size m×n (indexed by rows first). The other arguments are dummy arguments, you don't need to pass them in, they're just there to save bytes on declaring variables. It writes each changed pair to STDOUT in the format row1,col1:row1,col1;, with the semicolon separating the pairs. Uses 0-based indexing.
#define A a[i*o+p
#define B A*c
f(m,n,a,i,j,o,p,b,c,d)int*a;{
int t(x){printf("%d,%d:%d,%d;",b?i:c+x,b?c+x:i,b?i:c+1+x,b?c+1+x:i);}
o=n;p=b=1;for(;~b;b--){
for(i=0;i<m;i++){c=j=0;
for(;j<n;)c+=A*j++];d=c*n%3;
for(j=0;j<n-1;j++)
while(A*j]^d|A*j+p]^d){
for(c=j;B]==B+p];c++);
if(c<n-2&B]==d&2*(B+p]+A*(c+2)])%3==d)
B+p]=A*(c+2)]=d,t(1);else
B]=B+p]=2*(B]+B+p])%3,
t(0);}}o=m;p=m=n;n=o;o=1;}}
I used a slightly different algorithm than OP for solving individual rows/columns. It goes something like this(pseudocode):
for j in range [0, rowlength):
while row[j] != targetCol or row[j+1] != targetCol:
e=j
while row[e] == row[e+1]:
e++ //e will never go out of bounds
if e<=rowLength-3 and row[e] == targetCol
and (row[e+1] != row[e+2] != targetCol):
row.changeColor(e+1, e+2)
else:
row.changeColor(e, e+1)
The for(;~b;b--) loop executes exactly twice, on the second pass it solves columns instead of rows. This is done by swapping n and m, and changing the values of o and p which are used in pointer arithmetic to address the array.
Here's a version that's ungolfed, with a test main, and prints the whole array after every move (press enter to step 1 turn):
#define s(x,y)b?x:y,b?y:x
#define A a[i*o+p
#define B A*e
f(m,n,a,i,j,o,p,b,c,d,e)int*a;{
int t(x){
printf("%d,%d:%d,%d;\n",s(i,e+x),s(i,e+1+x));
getchar();
printf("\n");
for(int i2=0;i2<(b?m:n);i2++){
for(int j2=0;j2<(b?n:m);j2++){
printf("%d ",a[i2*(b?n:m)+j2]);
}
printf("\n");
}
printf("\n");
}
printf("\n");
b=1;
for(int i2=0;i2<(b?m:n);i2++){
for(int j2=0;j2<(b?n:m);j2++){
printf("%d ",a[i2*(b?n:m)+j2]);
}
printf("\n");
}
printf("\n");
o=n;p=1;
for(b=1;~b;b--){
for(i=0;i<m;i++){
c=0;
for(j=0;j<n;j++) c+= a[i*o+p*j];
d=0;
d = (c*n)%3;
for(j=0;j<n-1;j++) {
while(a[i*o+p*j]!=d||a[i*o+p*j+p]!=d){
for(e=j;a[i*o+p*e]==a[i*o+p*e+p];e++);
if(e<=n-3 && a[i*o+p*e]==d
&& 2*(a[i*o+p*e+p]+a[i*o+p*(e+2)])%3==d){
a[i*o+p*e+p]=a[i*o+p*(e+2)]=d;
t(1);
}else{
a[i*o+p*e]=a[i*o+p*e+p] = 2*(a[i*o+p*e]+a[i*o+p*e+p])%3;
t(0);
}
}
}
}
o=m;p=m=n;n=o;o=1;
}
}
main(){
int g[11][11] =
{
{0,2,1,2,2,1,0,1,1,0,2},
{2,1,1,0,1,1,2,0,2,1,0},
{1,0,2,1,0,1,0,2,1,2,0},
{0,0,2,1,2,0,1,2,0,0,1},
{0,2,1,2,2,1,0,0,0,2,1},
{2,1,1,0,1,1,2,1,0,0,2},
{1,0,2,1,0,1,0,2,2,1,2},
{0,0,2,1,2,0,1,0,1,2,0},
{1,2,0,1,2,0,0,2,1,2,0},
{2,1,1,0,1,1,2,1,0,0,2},
{0,2,1,0,1,0,2,1,0,0,2},
};
#define M 4
#define N 7
int grid[M][N];
for(int i=0;i<M;i++) {
for(int j=0;j<N;j++) {
grid[i][j] = g[i][j];
}
}
f(M,N,grid[0],0,0,0,0,0,0,0,0);
};
Lua, 594 575 559 Bytes
Warning There's still lots of work before I'm done with this golfing! I should be able to take that under 500 Bytes, at the very least. For the moment, it's the first solution that worked, and I'm still working on it.
I will provide a full explanation once I'm done.
function f(t)s=#t a=","for i=1,s do p=t[i]for i=1,s
do p.Q=p.Q and p.Q+p[i]or p[i]end p.Q=(p.Q*#p)%3 for i=1,s do for j=1,#p-1 do
x=p[j]y=p[j+1]u=x~=y and(p.S and p.R==p.S or x~=p.Q)v=(x+y)*2p[j]=u and v%3or x
p[j+1]=u and v%3or y print(i..a..j,i..a..j+1)end
p.R=p.S p.S=table.concat(p)end end
for i=1,s do Q=Q and Q+t[i][1]or t[i][1]end Q=(Q*s)%3 for i=1,s
do for j=1,s-1 do p=t[j]q=t[j+1]x=p[1]y=q[1]u=x~=y and(S and R==S or x~=Q)v=(x+y)*2
for k=1,#p do p[k]=u and v%3or x q[k]=u and v%3or y
print(j..a..k,j+1..a..k)end Y=Y and Y..x or x end
R=S S=Y end end
Octave, 334 313 bytes
Since the challenge may seem a bit daunting, I present my own solution. I did not formally prove that this method works (I guess that will come down to proving that the algorithm will never get stuck in a loop), but so far it works perfectly, doing 100x100 testcases within 15 seconds. Note that I chose to use a function with side effects rather than one that returns all the coordinates since that saved me a few bytes. Coordinates are row-major, 1-based, and formatted as row1 col1 row2 col2. Input colours are 0,1,2 since this works better with mod, at the cost of having to use numel rather than nnz. Golfed version: Edit: saved another few bytes by using a technique from Kevin Lau's answer.
function P(p)
k=0;[m,n]=size(p);t=@(v)mod(sum(v)*numel(v),3);for c=1:n
p(:,c)=V(p(:,c));end
k=1;for r=1:m
p(r,:)=V(p(r,:));end
function a=V(a)
while any(a-(g=t(a)))
isempty(q=find(diff(a)&a(1:end-1)-g,1))&&(q=find(diff(a),1));
a([q q+1])=t(a([q q+1]));if k
disp([r q r q+1])
else
disp([q c q+1 c])
end;end;end;end
Example GIF of the solving algorithm:
Ungolfed version:
function solveChromaticPuzzle(p)
[m,n]=size(p); % Get size
t=@(v)mod(sum(v)*numel(v),3); % Target colour function
for c=1:n % Loop over columns
p(:,c)=solveVec(p(:,c)); % Solve vector
end
for r=1:m % Loop over rows
p(r,:)=solveVec(p(r,:));
end
function a=solveVec(a) % Nested function to get globals
g=t(a); % Determine target colour
while(any(a~=g)) % While any is diff from target...
% Do the finding magic. Working left-to-right, we find the
% first pair that can be flipped (nonzero diff) that does not
% have the left colour different from our goal colour
q=min(intersect(find(diff(a)),find(a~=g)));
if(isempty(q)) % In case we get stuck...
q=find(diff(a),1); % ... just flip the first possible
end;
a([q q+1])=t(a([q q+1])); % Do the actual flipping.
if(exist('r')) % If we're working per row
disp([r q r q+1]) % Print the pair, using global row
else
disp([q c q+1 c]) % Print the pari, using global col
end
end
end
end
Befunge, 197 368 696 754 Bytes
(yes, I'm doing some reverse code golf, the more bytes the better)
I was thinking it could be a challenge to write this algorithm in Befunge and that it could be fun
I would like it to be a community program, so if anyone wants to work on it, please, do so.
In the end, I made everything alone so far, so I'll finish on my own (it's almost done)
What's done yet: a troll-shaped code
&:19p&:09p:v:p94g92g90 <
v94+1:g94&_$59g1+59p1-:|
>p59gp1-: ^ vp95g93$<
v94\-1<v:g< > v
>g:1+v^_$v^90p94g92<
v5p94< 3>1+59p ^
>9gg+\:^ %g v93:g95< v3_2 v
v1pg95g94<^95<>g-v>$v^ v ^-%3*2\gg9<
>9g39g+59g-1-|v-1_^ #^pg95+g92g90<1_09g:29g+5^
; > > 09g:29g+59gg\3%-# !^v <
^p95< ^ <
v p96-1+g90g92<
v p95_@
>59g1+:39g-19g-^
v >p 79g:59gg\1+59gp$$$$$29g49pv
> p59g^ |<<<<<<<<<<<<<<<<<<!-g96g94<
>:79^>29g49p>69g1+59gg49g:59gg\1+49p- v
^\-\6+gg95+1\g< v !-g96:<-1g94_^
>"]",52*,::59g^v_::1+59gg\59gg-v^ <
^ .-g93g95,.-g<>:69g- v v-g96:_1+^
>+" [,]",,,\29^ >#v_$:49g2-v
^1:.-g93g95,.-g92\,"[ ":< <
(yes, it's a troll, believe me)
Basically, it reads an array and computes the move to do to solve the rows, given an input as
(number of rows) (number of columns) 1 2 3 1 1 3 2 1 2 ....
(the whole array is passed as a list [row1, row2, row3,…])
output is
[col row],[col',row']
[col2 row2],[col2',row2']
...
rows and cols both start at 0.
Now that rows are solved, it's almost done ! Hooray !
Explanation: (will be updated later on)
So there are 5 main parts :
- The first one, in green, reads the input line and writes one row of the array
- The second one, in orange, passes to the next row of the array
- The third, in the blue, sums a row
- The fourth one, in hot pink, takes the modulus 3 of the sum, saves it at the right of the concerned row, and go to the next row
- Finally, in the red, the part that computes the target color from the previously computed number. This part is really dumb and should probably be rewritten, but I didn't figure out how I could do that in a nice way (passed from 197 bytes to 368 with just that part)
Grey parts are initialisations
Here is a a deeper explanation of the module that finds the to boxes to combine (which is coded here, by the way)
B
@ v
| !-g96g94<
ENTRY>29g49p>69g1+59gg49g:59gg\1+49p- v
v !-g96:<-1g94_^
v_::1+59gg\59gg-v^ <
>:69g- v v-g96:_1+^
>#v_$:49g2-v
CALL< <
The CALL part is when the instruction pointer is going to another module, to combine to boxes. It comes back to this module through the 'B' entry
Here is some pseudo code: (currentx is related to the array reading) For:
69g1+59gg // read target color
49g:59gg\1+49p // read current color and THEN shift the currentx to the next box
if ( top != top ){ // if the current color is bad
49g1- // put the current place (or currentx - 1) in the stack
While:
if ( :top != 69g ){ // if you didn't reach the end of the list
::1+ // copy twice, add 1
if ( 59gg == \59gg ){ // if the next color is the same than current
1+ // iterate
break While;
}
}
: // copies j (the previous raw iterator)
if ( top == 69g ){ // if you reached the end of the row (which mean you can't swap with the color after that point)
$: // discard j's copy and copy target
49g2- // put the place just before the color change on the stack
combine_with_next;
} else {
combine_with_next;
}
29g49p // back to the beginning of the row (there was some changes int the row)
}
if ( 49g != 69g ) // if you didn't reach the end of the list
break For:
Note that if you want to test it, you will have to put some trailing space and trailing new lines so that there is enough space to store the array, if you wish to use the interpret I linked. 22 + the number of rows in input as trailing lines, and 34 + the number of columns as trailing spaces on one line should be ok.
Rust, 496 495 bytes
Sadly I can't beat OP, but for a Rust answer I am quite satisfied with the bytecount.
let s=|mut v:Vec<_>,c|{
let p=|v:&mut[_],f,t|{
let x=|v:&mut[_],i|{
let n=v[i]^v[i+1];v[i]=n;v[i+1]=n;
for k in f..t+1{print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});}};
let l=v.len();let t=(1..4).find(|x|l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
let mut i=0;while i<l{let c=v[i];if c==t{i+=1;}else if c==v[i+1]{
let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};x(v,j);}else{x(v,i);}}t};
p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|{p(x,i,i)}).collect::<Vec<_>>(),0,c-1usize)};
Input: a vector of numbers as well as the number of columns. E.g.
s(vec!{1,2,1,3},2);
outputs
(row1,col1,row2,col2)
to the command line.
I first solve every row and then solve the resulting column only once ,but print the steps for all columns. So it is actually quite efficient :-P.
With formating:
let s=|mut v:Vec<_>,c|{
let p=|v:&mut[_],f,t|{ // solves a single row/column
let x=|v:&mut[_],i|{ // makes a move and prints it
let n=v[i]^v[i+1]; // use xor to calculate the new color
v[i]=n;
v[i+1]=n;
for k in f..t{
print!("{:?}",if f==t{(k,i,k,i+1)}else{(i,k,i+1,k)});
}
};
let l=v.len();
// find target color
// oh man i am so looking forward to sum() being stabilized
let t=(1..4).find(|x|(l*x)%3==v.iter().fold(0,|a,b|a+b)%3).unwrap();
let mut i=0;
while i<l{
let c=v[i];
if c==t{ // if the color is target color move on
i+=1;
}else if c==v[i+1]{ // if the next color is the same
// find the next possible move
let j=if let Some(x)=(i+1..l).find(|j|v[j+1]!=c){x}else{i-=1;i};
x(v,j);
}else{ // colors are different so we can make a move
x(v,i);
}
}
t
};
// first solve all rows and than sovle the resulting column c times
p(&mut (0..).zip(v.chunks_mut(c)).map(|(i,x)|p(x,i,i)).collect::<Vec<_>>(),0,c-1usize)
};
Edit: now returns the color of the solution which saves me a semicolon^^
Ruby, 266 bytes
More-or-less just a port of the Octave solution, except it solves rows first instead of columns. Input is an array of arrays, with the inner arrays being the rows. Output moves are [row, column, row, column]. Test suite
->m{t=->v{v.size*v.inject(:+)%3}
s=->a,x,r{g=t[a]
(q=(r=0..a.size-2).find{|i|a[i]!=a[i+1]&&g!=a[i]}||r.find{|i|a[i]!=a[i+1]}
a[q,2]=[t[a[q,2]]]*2
p r ?[x,q,x,q+1]:[q,x,q+1,x])while[]!=a-[g]}
m.size.times{|i|s[m[i],i,1]}
m=m.shift.zip *m
m.size.times{|i|s[m[i],i,p]}}
Ungolfed with explanation
->m{ # Start lambda function, argument `m`
t=->v{v.size*v.inject(:+)%3} # Target color function
s=->a,x,r{ # Function to determine proper moves
# a = row array, x = row index, r = horizontal
g=t[a] # Obtain target color
(
q=(r=0..a.size-2).find{|i| # Find the first index `i` from 0 to a.size-2 where...
a[i]!=a[i+1] # ...that element at `i` is different from the next...
&&g!=a[i] # ...and it is not the same as the target color
} || r.find{|i|a[i]!=a[i+1]} # If none found just find for different colors
a[q,2]=[t[a[q,2]]]*2 # Do the color flipping operation
p r ?[x,q,x,q+1]:[q,x,q+1,x] # Print the next move based on if `r` is truthy
) while[]!=a-[g]} # While row is not all the same target color, repeat
m.size.times{|i| # For each index `i` within the matrix's rows...
s[m[i],i,1] # ...run the solving function on that row
# (`r` is truthy so the moves printed are for rows)
}
m=m.shift.zip *m # Dark magic to transpose the matrix
m.size.times{|i|s[m[i],i,p]}} # Run the solving function on all the columns now
# (`r` is falsy so the moves printed are for columns)