7
\$\begingroup\$

Your Task

Given a list of words, check if they form a valid word grid. They form a valid grid if there are N words with N letters and they spell the same words vertically as they do horizontally. The words can be given in any order. [FILE, ICED, LEAD, EDDY] = True and [FILE, LEAD, EDDY, ICED] = True. Print True if it is valid or False if it is not

Here's some more examples

F I L E
I C E D
L E A D
E D D Y

O G R E        
G A I A       
R I G S        
E A S Y        

C A M P
A X E L
M E M O
P L O W

S P A S M
P A S T A
A S P E N
S T E E L
M A N L Y

This is code golf so lowest bytes wins

\$\endgroup\$
  • \$\begingroup\$ So we have to check all permutations of the input right? \$\endgroup\$ – Maltysen Jul 22 '15 at 19:44
  • \$\begingroup\$ @Maltysen Correct. Permutations of the words not the letters in the words \$\endgroup\$ – SirParselot Jul 22 '15 at 19:46
  • 7
    \$\begingroup\$ Any truthy/falsy values are fine, or the exact strings "True" and "False" ? \$\endgroup\$ – Optimizer Jul 22 '15 at 19:51
  • 2
    \$\begingroup\$ @SirParselot Probably because they find the challenge is fairly trivial / uninteresting. \$\endgroup\$ – Kade Jul 22 '15 at 20:24
  • 2
    \$\begingroup\$ @SirParselot I might also guess someone is unhappy their language has to convert to True/False while others have them natively. \$\endgroup\$ – xnor Jul 23 '15 at 1:51

13 Answers 13

7
\$\begingroup\$

Pyth - 10 9 bytes

The actual check is very easy, in just three bytes with CIQ. The permutation part takes the other 6.

.EmCId.pQ

Try it online here.

It maps over the .permutations of the (Q) input, each time checking if the loop var(d) is Invarient under (C) rotation. Then it checks if .Eany are true.

\$\endgroup\$
5
\$\begingroup\$

CJam (25 24 bytes)

q~e!{_z=},"True""False"?

Online demo. Pretty trivial apart from the specified output, because CJam doesn't have a Boolean type.

With thanks to Sp3000 for saving one stroke.

\$\endgroup\$
  • \$\begingroup\$ @Sp3000, true. I'm so used to expecting the interleaved string approach to be shorter that I didn't even try the naïve approach. \$\endgroup\$ – Peter Taylor Jul 22 '15 at 20:09
  • \$\begingroup\$ Has Peter abandoned GolfScript in favor of CJam?? \$\endgroup\$ – Alex A. Jul 22 '15 at 20:17
  • \$\begingroup\$ @AlexA., not entirely. But for this question, GS can't possibly get anywhere near CJam. e! would require writing a recursive function in GS: that's 6 characters before it even does anything. \$\endgroup\$ – Peter Taylor Jul 22 '15 at 20:22
4
\$\begingroup\$

Julia, 114 bytes

Did somebody say "super long solution"?? It just so happens that I have one for you.

a->(L=length(a);P(x)=reshape(split(join(x),""),L,L);print(any([P(p)==P(p)'for p=permutations(a)])?"True":"False"))

This creates an unnamed function that accepts an array and prints to stdout. It works by generating all permutations, turning the arrays into matrices of letters and checking whether each matrix is equal to its transpose. Unfortunately booleans are lowercase in Julia, otherwise I wouldn't have had to do the ternary.

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

Haskell, 51 bytes

import Data.List
any((==)=<<transpose).permutations

Usage example: any((==)=<<transpose).permutations $ ["LEAD","FILE","ICED","EDDY"] -> True.

How it works: check if any of the permutations equals it's transposition. Luckily Haskell's native boolean values are True and False.

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

Python 2, 87 85 Bytes

Straightforward solution using zip() to transpose.

Saved two bytes on both thanks to xnor.

from itertools import*
print any(zip(*c)==map(tuple,c)for c in permutations(input()))

Solution without relying on imports, 139 138 136 Bytes

p=lambda l:[[j]+k for i,j in enumerate(l)for k in p(l[:i]+l[-~i:])]if~-len(l)else[l]
print any(zip(*c)==map(tuple,c)for c in p(input()))

If there's a way to get around using enumerate, let me know! :)

Input for both should be formatted like so:

["FILE","ICED","EDDY","LEAD"]

Psst. Hey! Here's a solution in Symbolic, something I'm working on. Ƥ(Ʌ(ʐ(*c)==ϻ(ϰ,c)ϝcϊƥ(Ί)))

\$\endgroup\$
  • \$\begingroup\$ You can do any() for sum()>0. \$\endgroup\$ – xnor Jul 22 '15 at 22:07
  • \$\begingroup\$ are you submitting this for the bounty? \$\endgroup\$ – Maltysen Jul 23 '15 at 1:49
  • \$\begingroup\$ @Maltysen No, I just did it because I was experimenting :) \$\endgroup\$ – Kade Jul 23 '15 at 1:55
  • \$\begingroup\$ Symbolic looks really cool! But fyi, the 31 characters in that solution make for a score of 41 bytes in UTF-8. It may not be the most competitive golfing language. ;) \$\endgroup\$ – Alex A. Jul 23 '15 at 15:20
  • \$\begingroup\$ @AlexA. I don't think I could make anything on the level of Pyth/CJam/GolfScript, I'm just doing it for fun ;P \$\endgroup\$ – Kade Jul 23 '15 at 15:22
2
\$\begingroup\$

Python 2, 74

s=input().split()
print all(''.join(s)[s.index(w)::len(w)]in s for w in s)
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 6 bytes

p⟨\=≡⟩

Try it online!

Assuming output can be "true." and "false." instead of "True" and "False".

If not, it's a trivial change to:

22 bytes

p⟨\=≡⟩∧"True"|∧"False"

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Mathematica (48 42 bytes)

Or@@(#==#&/@Characters@Permutations@#)&

Luckily Transpose can be represented by a single unicode character.

\$\endgroup\$
  • \$\begingroup\$  is this the character for transpose? I found a different one on wolfram's website \$\endgroup\$ – SirParselot Jul 22 '15 at 20:42
  • \$\begingroup\$ Yes, U+F3C7. But it actually doesn't render correctly on my system. Copy&Pasting the code however works fine. \$\endgroup\$ – murphy Jul 22 '15 at 20:52
1
\$\begingroup\$

JavaScript ES6, 90 58 bytes

s=>s.every((l,i)=>s.map(p=>p[i]).join``==l)?'True':'False'

Old answer:

s=>~(n=s.split`
`).map((l,i)=>n.map(p=>p[i*2]).join` `==l).indexOf(!1)?'False':'True'

The newline is significant and counts as a byte.


ES5 Demo:

function t(s) {
    return ~(n=s.split('\n')).map(function(l,i){return n.map(function(p){return o=p[i*2]}).join(' ')==l}).indexOf(!1)?'False':'True'
}

// Demo
document.getElementById('go').onclick=function(){
  document.getElementById('output').innerHTML = t(document.getElementById('input').value)
};
<div style="padding-left:5px;padding-right:5px;"><h2 style="font-family:sans-serif">Word Grids Snippet</h2><div><div  style="background-color:#EFEFEF;border-radius:4px;padding:10px;"><textarea placeholder="Text here..." style="resize:none;width:70px;height:70px;border:1px solid #DDD;" id="input"></textarea><button id='go'>Run!</button></div><br><div style="background-color:#EFEFEF;border-radius:4px;padding:10px;"><span style="font-family:sans-serif;">Output:</span><br><pre id="output" style="background-color:#DEDEDE;padding:1em;border-radius:2px;overflow-x:auto;"></pre></div></div></div>

\$\endgroup\$
  • \$\begingroup\$ Note: The code snippet will only return true if there is a single space between each letter in the code grid, as in the OP examples. \$\endgroup\$ – Ayelis Jul 22 '15 at 23:02
1
\$\begingroup\$

Ruby, 97 bytes

91 bytes if we remove .chomp inside map

a=gets.chomp.split','.map{|_|_.chomp.chars};p a.permutation.map{|p|p[0].zip(*p[1..-1])===p}.any?
\$\endgroup\$
1
\$\begingroup\$

MATLAB - 75 98 bytes

Note: I didn't see that you had to output True or False, so I had to create an additional cell array that stores these two choices then we choose from this array when we're done.


This is a rather brute-force solution. This assumes that you have loaded A in as a character matrix and that A is symmetric in size (i.e. # of rows is equal to # of columns):

c={'False','True'};o=0;for k=perms(1:size(A,1))'o=o|sum(sum(A(k,:)==A(k,:)'))==numel(A);end,c{o+1}

The overall process is to first create a 2D array of all possible permutations that goes from 1 up to as many words as we have N. Each row of this matrix gives you a permutation enumerated from 1 up to N, and we can check either the number of rows or columns for the value N. Next, we go through every possible permutation and rearrange the matrix A's rows based on the permutation vector produced by that permutation. For example, if N=4, and if we had [1,4,2,3] as the permutation vector, it would rearrange the matrix A so that row 1 of the original matrix A appears first, followed by row 4 of the original matrix A appearing second, row 2 of the original matrix A appearing third and finally row 3 of the original matrix A appearing last.

The above problem is essentially checking to see that if we all of these matrix rearrangements for A over all possible permutations, we check to see if this rearranged matrix is equal to its transpose. In order to facilitate this, I do an element-by-element equality check of the characters, and sum over this result. If the sum is equal to the total size of the matrix, then we have a true result. This code will check all possible permutations, even if we have found a match before we exhaust all possibilities. The statement o=0 is an indicator variable o that tells us whether we have found the condition being true or false.

Inside the loop, we keep updating o and checking for the above summation condition by logical ORing with the current result and with the current rearranged matrix condition. It will be set to true if we have found such a condition or it gets to 1, and will stay false if we don't, or stays at 0.

Minor Note

The for loop behaviour is rather undocumented, but if you specify a matrix to be what is iterating over the for loop, each value k would be a column of the said matrix. For example, if we did:

B = [0 0 0 0; 1 1 1 1; 2 2 2 2; 3 3 3 3];
for k = B
    disp(k);
end

We would select out the first column of B, display it, then the next column of B, display it, etc... so you would get a series of [0,1,2,3]'s.


Example Runs

>> A = ['FILE'; 'ICED'; 'LEAD'; 'EDDY'];
>> c={'False','True'};o=0;for k=perms(1:size(A,1))'o=o|sum(sum(A(k,:)==A(k,:)'))==numel(A);end,c{o+1}

ans =

    True

>> A = ['FILE'; 'LEAD'; 'EDDY'; 'ICED'];
>> c={'False','True'};o=0;for k=perms(1:size(A,1))'o=o|sum(sum(A(k,:)==A(k,:)'))==numel(A);end,c{o+1}

ans =

    True

>> A = ['OGRE'; 'GAIA'; 'RIGS'; 'EASY'];
>> c={'False','True'};o=0;for k=perms(1:size(A,1))'o=o|sum(sum(A(k,:)==A(k,:)'))==numel(A);end,c{o+1}

ans =

    True

>> A = ['CAMP', 'AXEL', 'MEMO', 'PLOW'];
>> c={'False','True'};o=0;for k=perms(1:size(A,1))'o=o|sum(sum(A(k,:)==A(k,:)'))==numel(A);end,c{o+1}

ans =

    True

>> A = ['SPASM', 'PASTA', 'ASPEN', 'STEEL', 'MANLY'];
>> c={'False','True'};o=0;for k=perms(1:size(A,1))'o=o|sum(sum(A(k,:)==A(k,:)'))==numel(A);end,c{o+1}

ans =

    True

Just to be sure, here's an example of where it shouldn't work:

>> A = ['CBMP'; 'APEL'; 'MCTO'; 'DLOX'];
>> A

A =

CBMP
APEL
MCTO
DLOX

>> c={'False','True'};o=0;for k=perms(1:size(A,1))'o=o|sum(sum(A(k,:)==A(k,:)'))==numel(A);end,c{o+1}

ans =

    False
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 11 bytes

øQi”‰¦”딞ä

Try it online.

Explanation:

ø        # Zip the (implicit) input, swapping columns and rows
 Q       # Check if it is equal to the (implicit) input
         # That's it, we're done.. If it weren't for the requirement of explicitly 
         # outputting the strings "True"/"False" instead of a truthy/falsey result..

i        # If the result is 1 (truthy):
 ”‰¦”    #  Output "True"
ë        # Else:
 ”žä     #  Output "False"

See here to understand why ”‰¦” is True and ”žä is False.


11 bytes alternative:

øQ”žä‰¦”#sè

Try it online.

\$\endgroup\$
0
\$\begingroup\$

Java (OpenJDK 8), 134 bytes

a->{int b=a.length,i=0,j=0;for(;i++<b;){for(;j<b;j++){if(a[j].length()!=b||a[i].charAt(j)!=a[j].charAt(i))return false;}}return true;}

Try it online!

Explanation:

int b=a.length,i=0,j=0;                               //Create Variables
for(;i++<b;){for(;j<b;j++){                           //Nested Loop
if(a[j].length()!=b||a[i].charAt(j)!=a[j].charAt(i))  //Is the grid valid?
    return false;                                     //if not, return false
}}
return true;                                     //if it gets this far, return true
\$\endgroup\$
  • \$\begingroup\$ Is this work with "The words can be given in any order." rule? \$\endgroup\$ – mazzy Aug 13 '18 at 11:15

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.