Teilen Sie ein Wort in Teile mit gleichen Punktzahlen

9

Unter der Annahme, dass A = 1, B = 2 ... Z = 26 und der Wert eines Wortes die Summe dieser Buchstabenwerte ist, ist es möglich, einige Wörter in zwei Teile zu teilen, so dass sie gleiche Werte haben.

Zum Beispiel kann "wordsplit" wie folgt in zwei Teile zerlegt werden: ordsl wpit, weil o + r + d + s + l = w + p + i + t.

Dies war eine Herausforderung, die uns mein Computerlehrer gegeben hat - es ist anscheinend eine alte Herausforderung der Lionhead Studios. Ich habe es in Python gelöst und werde meine Antwort in Kürze veröffentlichen.

Herausforderung: Das kürzeste Programm, das alle möglichen Teilungen mit gleichen Punktzahlen auflisten kann. Beachten Sie, dass für jede Buchstabengruppe nur einer aufgelistet werden muss - ordsl wpit ist beispielsweise dasselbe wie rdosl wtip. Es ist einfacher, sie in der Reihenfolge aufzulisten, in der sie im Wort kommen.

Bonus:

  • Wenn Sie Paare markieren, bei denen beide Wörter gültige englische Wörter sind (oder eine Permutation der Buchstaben ist), verwenden Sie eine Wortliste. (Dies kann durch Platzieren eines Sternchens neben jeder oder einer anderen Methode erfolgen, aber machen Sie es deutlich.)
  • Hinzufügen der Option zum Entfernen von Duplikaten (dies sollte nicht die Standardeinstellung sein.)
  • Unterstützung von mehr als zwei Teilungen, z. B. drei, vier oder sogar n-Wege-Teilungen.
Thomas O.
quelle
Muss das Programm die Eingabe gemischter Groß- und Kleinschreibung unterstützen? Und wenn ja, kann es den Fall für die Ausgabe verwerfen?
Nemo157
@ Nemo157 Groß- und Kleinschreibung wird möglicherweise ignoriert und muss nicht in der Ausgabe gespeichert werden.
Thomas O
Kann das Programm zusätzliches Material ausgeben, solange der angeforderte Teil der Ausgabe für einen Menschen klar ist?
JB
@JB Ja, das kann es.
Thomas O
ok, ich werde das Perl dann verbessern;) Danke
JB

Antworten:

4

Perl, 115 118 123

@_=~/./g;for$i(1..1<<@_){$l=$
r;$i&1<<$_?$l:$r+=64-ord$_[$_
]for 0..$#_;$l-$r||$i&1<<$_&&
print$_[$_]for 0..$#_;say""}

Laufen Sie mit perl -nE '<code goes here>' . Dieses 'n' wird in der Codegröße gezählt.

Respaced:

@_ = /./g;
for $i (1 .. 1<<@_) {
  $l = $r;
  $i & 1<<$_ ? $l : $r -= 64 - ord $_[$_] for 0 .. $#_;

  $l - $r      ||
  $i & 1<<$_   &&
  print $_[$_]
    for 0 .. $#_;

  say ""
}

Mit Kommentaren und Variablennamen:

# split a line of input by character
@chars = /./g;

# generate all binary masks of same length
for $mask (1 .. 1<<@_) {

  # start at "zero"
  $left_sum = $right_sum;

  # depending on mask, choose left or right count
  # 1 -> char goes left; 0 -> char goes right
  $mask & 1<<$_ ? $left_sum : $right_sum
    -= 64 - ord $chars[$_]   # add letter value
      for 0 .. $#chars;      # for all bits in mask

  # if left = right
  $left_sum - $right_sum ||

  # if character was counted left (mask[i] = 1)
  $mask & 1<<$_          &&

  # print it
  print $chars[$_]

  # ...iterating on all bits in mask
    for 0 .. $#chars;

  # newline
  say ""
}

Einige der verwendeten Tricks:

  • 1..1<<@_ deckt den gleichen Bitbereich ab wie 0..(1<<@_)-1 , ist jedoch kürzer. (Beachten Sie, dass die Betrachtung des Problems aus größerer Entfernung, einschließlich der mehrfachen Bereichsgrenzen, ohnehin nicht zu einer falschen Ausgabe führen würde.)
  • $ left_range und $ right_range werden nicht auf die tatsächliche numerische Null "0" zurückgesetzt: Da wir sie am Ende nur akkumulieren und vergleichen, müssen sie nur mit demselben Wert beginnen.
  • Subtrahieren 64-ord$_[$_]statt Addieren ord$_[$_]-64gewinnt ein unsichtbares Zeichen: Da es mit einem Trennzeichen endet, wird das Leerzeichen davor gesetztfor unnötig.
  • Mit Perl können Sie einer Variablen zuweisen, die vom ternären bedingten Operator bestimmt wird : cond ? var1 : var2 = new_value.
  • Boolesche Ausdrücke gekettet mit &&und ||werden anstelle von richtigen conditionals verwendet.
  • $l-$r ist kürzer als $l!=$r
  • gibt eine neue Zeile aus, auch bei Teilungen, die nicht ausgeglichen sind. Leere Zeilen sind nach den Regeln in Ordnung! Ich habe gefragt!
JB
quelle
Möchten Sie es für diejenigen von uns erklären, die kein Leitungsrauschen sprechen? Es sieht so aus, als würden Sie einen binären Maskenansatz verwenden, der meinem ähnlich ist, und ich sehe, dass 64 '@' = 'A' - 1 bedeutet, und danach bin ich ziemlich verloren.
dmckee --- Ex-Moderator Kätzchen
Ist diese Bearbeitung besser?
JB
Nett. Ich muss darüber nachdenken, die Addition jeder Zählung zur linken oder rechten Summe zu nutzen. Hätte offensichtlich sein sollen, aber ich habe es verpasst.
dmckee --- Ex-Moderator Kätzchen
3

J (109)

~.(/:{[)@:{&a.@(96&+)&.>>(>@(=/@:(+/"1&>)&.>)#[),}.@(split~&.>i.@#@>)@<@(96-~a.&i.)"1([{~(i.@!A.i.)@#)1!:1[1

Ausgabe für wordsplit:

┌─────┬─────┐
│lorw │dipst│
├─────┼─────┤
Iltdiltw│oprs │
├─────┼─────┤
│iptw │dlors│
├─────┼─────┤
Ldlors│iptw │
├─────┼─────┤
│oprs │diltw│
├─────┼─────┤
IpDipst│lorw │
└─────┴─────┘

Erläuterung:

  • 1!:1[1: lese eine Zeile von stdin
  • ([{~(i.@!A.i.)@#): Holen Sie sich alle Permutationen
  • "1: für jede Permutation:
  • (96-~a.&i.): Buchstabenwerte erhalten
  • }.@(split~&.>i.@#@>)@<: Teilen Sie jede Permutation der Partituren an jedem möglichen Platz auf, außer vor der ersten und nach der letzten Zahl
  • >(>@(=/@:(+/"1&>)&.>)#[): Sehen Sie, welche Permutationen übereinstimmende Hälften haben, und wählen Sie diese aus
  • {&a.@(96&+)&.>: Verwandle die Partituren wieder in Buchstaben
  • ~.(/:{[): Entfernen Sie triviale Variationen (zB ordsl wpitund ordsl wpti)
Marinus
quelle
Einige Ihrer Antworten sind Duplikate.
DavidC
@ DavidCarraher: Nun, entweder bin ich blind oder dieser ist es nicht, noch sind meine letzten Antworten. Ich habe die Antworten anderer Leute nie absichtlich kopiert, obwohl Sie natürlich Recht haben könnten. Ich habe hier manchmal gepostet, während ich betrunken war, und mich nicht daran erinnert, bis ich viele Downvotes bekam und es sich herausstellte, dass ich etwas eingereicht hatte, das nicht einmal war fast zu korrigieren. Wenn Sie gesehen haben, dass ich mich schlecht benehme, hinterlassen Sie vielleicht den Kommentar, in dem ich mich schlecht benehme. Dann werde ich alle beleidigenden Antworten löschen. oder vielleicht stimmen Sie sie ab, da dies der Grund ist.
Marinus
Es war kein geringes beabsichtigt. Ich habe zum Beispiel einfach gemeint, dass Ihre erste Antwort {"lorw", "dipst"} ein Duplikat Ihrer endgültigen Antwort {"dipst", "lorw"} ist. Nur die Reihenfolge der Wörter ist unterschiedlich.
DavidC
@DavidCarraher: whoops: PI dachte, Sie meinten, ich hätte die Antwort von jemandem kopiert ... trotzdem sagt diese Frage (wenn ich sie richtig interpretiert habe), um die Duplikate zu entfernen, bei denen die einzelnen Teile nur Permutationen voneinander sind, aber nicht zu entfernen diejenigen, bei denen die Reihenfolge der Teile unterschiedlich ist, dh wenn sie {a,bc}bereits gefunden wurden, entfernen, {a,cb}aber nicht entfernen {bc,a}. (Und natürlich bin ich nicht beleidigt, wenn ich tatsächlich jemandes Antwort / hatte / duplizierte, würde ich es vorziehen, wenn jemand darauf hinwies.)
Marinus
Sie scheinen recht zu haben. Die Anweisungen besagen, dass es in Ordnung ist, die Reihenfolge der Wörter zu ignorieren ("Beachten Sie, dass für jede Buchstabengruppe nur eine aufgeführt werden muss"), dies ist jedoch nicht erforderlich. Dies kann mir ein paar Zeichen ersparen. Vielen Dank.
DavidC
2

c99 - 379 notwendige Zeichen

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int s(char*w,int l,int m){int b,t=0;for(b=0;b<l;++b){t+=(m&1<<b)?toupper(w[b])-64:0;}return t;}
void p(char*w,int l,int m){for(int b=0;b<l;++b){putchar((m&1<<b)?w[b]:32);}}
int main(){char w[99];gets(w);int i,l=strlen(w),m=(1<<l),t=s(w,l,m-1);
for(i=0;i<m;i++){if(s(w,l,i)==t/2){p(w,l,i);putchar(9);p(w,l,~i);putchar(10);}}}

Der Ansatz ist ziemlich offensichtlich. Es gibt eine Funktion, die ein Wort nach einer Maske summiert und eine, die es auch nach einer Maske druckt. Eingabe von der Standardeingabe. Eine Kuriosität ist, dass die Druckroutine Leerzeichen für Buchstaben einfügt, die nicht in der Maske enthalten sind. Eine Registerkarte wird verwendet, um die Gruppen zu trennen.

Ich mache keinen der Bonusgegenstände und kann auch nicht einfach konvertiert werden, um sie zu unterstützen.

Lesbar und kommentiert:

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int s(char *w, int l, int m){ /* word, length, mask */
  int b,t=0;                  /* bit and total */
  for (b=0; b<l; ++b){        
/*     printf("Summing %d %d %c %d\n",b,m&(1<<b),w[b],toupper(w[b])-'A'-1); */
    t+=(m&1<<b)?toupper(w[b])-64:0; /* Add to toal if masked (A-1 = @ = 64) */
  }
  return t;
}
void p(char *w, int l, int m){
  for (int b=0; b<l; ++b){ 
    putchar((m&1<<b)?w[b]:32);  /* print if masked (space = 32) */
  }
}
int main(){
  char w[99];
  gets(w);
  int i,l=strlen(w),m=(1<<l),t=s(w,l,m-1);
/*   printf("Word is '%s'\n",w); */
/*   printf("...length %d\n",l); */
/*   printf("...mask   0x%x\n",m-1); */
/*   printf("...total  %d\n",t); */
  for (i=0; i<m; i++){
/*     printf("testing with mask 0x%x...\n",i); */
    if (s(w,l,i)==t/2) {p(w,l,i); putchar(9); p(w,l,~i); putchar(10);}
    /* (tab = 9; newline = 10) */
  }
}

Validierung

 $ wc wordsplit_golf.c
  7  24 385 wordsplit_golf.c
 $ gcc -std=c99 wordsplit_golf.c
 $ echo wordsplit | ./a.out
warning: this program uses gets(), which is unsafe.
 or sp          w  d  lit
wor   l            dsp it
 ords l         w    p it
w    p it        ords l  
   dsp it       wor   l  
w  d  lit        or sp   
dmckee --- Ex-Moderator Kätzchen
quelle
1

Rubin: 125 Zeichen

r=->a{a.reduce(0){|t,c|t+=c.ord-96}}
f=r[w=gets.chomp.chars]
w.size.times{|n|w.combination(n).map{|s|p([s,w-s])if r[s]*2==f}}

Probelauf:

bash-4.2$ ruby -e 'r=->a{a.reduce(0){|t,c|t+=c.ord-96}};f=r[w=gets.chomp.chars.to_a];w.size.times{|p|w.combination(p).map{|q|p([q,w-q])if r[q]*2==f}}' <<< 'wordsplit'
[["w", "o", "r", "l"], ["d", "s", "p", "i", "t"]]
[["w", "p", "i", "t"], ["o", "r", "d", "s", "l"]]
[["o", "r", "s", "p"], ["w", "d", "l", "i", "t"]]
[["w", "d", "l", "i", "t"], ["o", "r", "s", "p"]]
[["o", "r", "d", "s", "l"], ["w", "p", "i", "t"]]
[["d", "s", "p", "i", "t"], ["w", "o", "r", "l"]]
Mann bei der Arbeit
quelle
1

Mathematica 123 111

Findet alle Teilmengen von Wörtern, die 1/2 der "ascii total" des Wortes haben d. Findet dann die Ergänzungen dieser Teilmengen.

d = "WORDSPLIT"

{#, Complement[w, #]}&/@Cases[Subsets@#,x_/;Tr@x==Tr@#/2]&[Sort[ToCharacterCode@d - 64]];
FromCharacterCode[# + 64] & /@ %

{{"IPTW", "DLORS"}, {"LORW", "DIPST"}, {"OPRS", "DILTW"}, {"DILTW", "OPRS"}, {"DIPST", "LORW"} , {"DLORS", "IPTW"}}

DavidC
quelle
1

J, 66 Zeichen

Verwenden Sie Ziffern von base2-Zahlen, um jede mögliche Teilmenge auszuwählen.

   f=.3 :'(;~y&-.)"{y#~a#~(=|.)+/"1((+32*0&>)96-~a.i.y)#~a=.#:i.2^#y'
   f 'WordSplit'
┌─────┬─────┐
│Worl │dSpit│
├─────┼─────┤
│Wdlit│orSp │
├─────┼─────┤
│Wpit │ordSl│
├─────┼─────┤
│ordSl│Wpit │
├─────┼─────┤
│orSp │Wdlit│
├─────┼─────┤
│dSpit│Worl │
└─────┴─────┘
randomra
quelle
0

Meine Lösung ist unten. Es ist ein fast Anti-Golf in seiner Größe, aber es funktioniert sehr gut. Es unterstützt n-Wege-Teilungen (obwohl die Rechenzeit für mehr als 3 Teilungen sehr lang wird) und das Entfernen von Duplikaten.

class WordSplitChecker(object):
    def __init__(self, word, splits=2):
        if len(word) == 0:
            raise ValueError, "word too short!"
        if splits == 0:
            raise ValueError, "splits must be > 1; it is impossible to split a word into zero groups"
        self.word = word
        self.splits = splits

    def solve(self, uniq_solutions=False, progress_notifier=True):
        """To solve this problem, we first need to consider all the possible
        rearrangements of a string into two (or more) groups.

        It turns out that this reduces simply to a base-N counting algorithm,
        each digit coding for which group the letter goes into. Obviously
        the longer the word the more digits needed to count up to, so 
        computation time is very long for larger bases and longer words. It 
        could be sped up by using a precalculated array of numbers in the
        required base, but this requires more memory. (Space-time tradeoff.)

        A progress notifier may be set. If True, the default notifier is used,
        if None, no notifier is used, and if it points to another callable,
        that is used. The callable must take the arguments as (n, count, 
        solutions) where n is the number of iterations, count is the total 
        iteration count and solutions is the length of the solutions list. The
        progress notifier is called at the beginning, on every 1000th iteration, 
        and at the end.

        Returns a list of possible splits. If there are no solutions, returns
        an empty list. Duplicate solutions are removed if the uniq_solutions
        parameter is True."""
        if progress_notifier == True:
           progress_notifier = self.progress 
        solutions = []
        bucket = [0] * len(self.word)
        base_tuple = (self.splits,) * len(self.word)
        # The number of counts we need to do is given by: S^N,
        # where S = number of splits,
        #       N = length of word.
        counts = pow(self.splits, len(self.word))
        # xrange does not create a list in memory, so this will work with very
        # little additional memory.
        for i in xrange(counts):
            groups = self.split_word(self.word, self.splits, bucket)
            group_sums = map(self.score_string, groups)
            if len(set(group_sums)) == 1:
                solutions.append(tuple(groups))
            if callable(progress_notifier) and i % 1000 == 0:
                progress_notifier(i, counts, len(solutions))
            # Increment bucket after doing each group; we want to include the
            # null set (all zeroes.)
            bucket = self.bucket_counter(bucket, base_tuple)
        progress_notifier(i, counts, len(solutions))
        # Now we have computed our results we need to remove the results that
        # are symmetrical if uniq_solutions is True.
        if uniq_solutions:
            uniques = []
            # Sort each of the solutions and turn them into tuples.  Then we can 
            # remove duplicates because they will all be in the same order.
            for sol in solutions:
                uniques.append(tuple(sorted(sol)))
            # Use sets to unique the solutions quickly instead of using our
            # own algorithm.
            uniques = list(set(uniques))
            return sorted(uniques)
        return sorted(solutions)

    def split_word(self, word, splits, bucket):
        """Split the word into groups. The digits in the bucket code for the
        groups in which each character goes in to. For example,

        LIONHEAD with a base of 2 and bucket of 00110100 gives two groups, 
        "LIHAD" and "ONE"."""
        groups = [""] * splits
        for n in range(len(word)):
            groups[bucket[n]] += word[n]
        return groups

    def score_string(self, st):
        """Score and sum the letters in the string, A = 1, B = 2, ... Z = 26."""
        return sum(map(lambda x: ord(x) - 64, st.upper()))

    def bucket_counter(self, bucket, carry):
        """Simple bucket counting. Ex.: When passed a tuple (512, 512, 512)
        and a list [0, 0, 0] it increments each column in the list until
        it overflows, carrying the result over to the next column. This could
        be done with fancy bit shifting, but that wouldn't work with very
        large numbers. This should be fine up to huge numbers. Returns a new
        bucket and assigns the result to the passed list. Similar to most
        counting systems the MSB is on the right, however this is an 
        implementation detail and may change in the future.

        Effectively, for a carry tuple of identical values, this implements a 
        base-N numeral system, where N+1 is the value in the tuple."""
        if len(bucket) != len(carry):
            raise ValueError("bucket and carry lists must be the same size")
        # Increase the last column.
        bucket[-1] += 1 
        # Carry numbers. Carry must be propagated by at least the size of the
        # carry list.
        for i in range(len(carry)):
            for coln, col in enumerate(bucket[:]):
                if col >= carry[coln]:
                    # Reset this column, carry the result over to the next.
                    bucket[coln] = 0
                    bucket[coln - 1] += 1
        return bucket

    def progress(self, n, counts, solutions):
        """Display the progress of the solve operation."""
        print "%d / %d (%.2f%%): %d solutions (non-unique)" % (n + 1, counts, (float(n + 1) / counts) * 100, solutions) 

if __name__ == '__main__':
    word = raw_input('Enter word: ')
    groups = int(raw_input('Enter number of required groups: '))
    unique = raw_input('Unique results only? (enter Y or N): ').upper()
    if unique == 'Y':
        unique = True
    else:
        unique = False
    # Start solving.
    print "Start solving"
    ws = WordSplitChecker(word, groups)
    solutions = ws.solve(unique)
    if len(solutions) == 0:
        print "No solutions could be found."
    for solution in solutions:
        for group in solution:
            print group,
        print

Beispielausgabe:

Enter word: wordsplit
Enter number of required groups: 2
Unique results only? (enter Y or N): y
Start solving
1 / 512 (0.20%): 0 solutions (non-unique)
512 / 512 (100.00%): 6 solutions (non-unique)
dspit worl
ordsl wpit
orsp wdlit
Thomas O.
quelle
1
Meiner Meinung nach sind Antworten, die zugegebenermaßen keinen Versuch unternehmen, das Ziel der ursprünglichen Frage (Code-Kürze) zu erreichen, praktisch nicht zum Thema. Sie geben zu, dass diese Antwort keinen Bezug zu Code-Golf hat. Anstatt sie als Antwort zu veröffentlichen, würde ich vorschlagen, sie an einer anderen Stelle zu veröffentlichen und in einem Kommentar zur Frage einen Link dazu zu setzen.
Jeff Swensen
2
@Sugerman: Es ist eine Referenzimplementierung, kein Versuch, das Spiel zu gewinnen. Ich bevorzuge Referenzimplementierungen als Antworten, anstatt Platz oben auf der Seite einzunehmen, und ich bevorzuge sie vor Ort, um das Risiko von Linkfäule zu beseitigen.
dmckee --- Ex-Moderator Kätzchen
@Sugerman: Warum nicht einreichen? Es ist besser als nichts. Es könnte minimiert werden, aber warum sich die Mühe machen - ich kann meine eigene Frage nicht wirklich akzeptieren (nun, ich kann , aber es ist nicht im Geiste davon.)
Thomas O
Denn im Grunde ist dies eine Frage & Antwort-Seite. Etwas, das nicht als Antwort gedacht ist, sollte nicht als solches veröffentlicht werden.
Jeff Swensen
1
Wie ich in meinem ersten Kommentar sagte, hätte ich in einem Kommentar zur Frage darauf verlinkt oder den Link dort bearbeitet, da Ihnen die Frage gehört. Es ist auch nichts Falsches daran, eine Antwort auf Ihre eigene Frage zu senden, solange Sie Ihre eigene Antwort nicht automatisch akzeptieren, ohne alle anderen (und Abstimmungsergebnisse) zu berücksichtigen.
Jeff Swensen
0

Lua - 195

a=io.read"*l"for i=0,2^#a/2-1 do z,l=0,""r=l for j=1,#a do b=math.floor(i/2^j*2)%2 z=(b*2-1)*(a:byte(j)-64)+z if b>0 then r=r..a:sub(j,j)else l=l..a:sub(j,j)end end if z==0 then print(l,r)end end

Die Eingabe muss in Großbuchstaben erfolgen:

~$ lua wordsplit.lua 
>WORDSPLIT
WDLIT   ORSP
DSPIT   WORL
WPIT    ORDSL
mniip
quelle
0

Python - 127

w=rawinput()
for q in range(2**len(w)/2):
 a=[0]*2;b=['']*2
 for c in w:a[q%2]+=ord(c)-96;b[q%2]+=c;q/=2
 if a[0]==a[1]:print b

und hier eine n-split Version mit 182 Bytes ohne Duplikate:

n,w=input()
def b(q):
 a=[0]*n;b=['']*n
 for c in w:a[q%n]+=ord(c)-96;b[q%n]+=c;q/=n
 return a[0]==a[1] and all(b) and frozenset(b)
print set(filter(None,map(b,range(n**len(w)/n))))

Eingabe ist zB:

3, 'wordsplit'
Daniel
quelle