Podziel słowo na części z jednakowymi wynikami

9

Zakładając, że A = 1, B = 2 ... Z = 26, a wartość słowa jest sumą tych wartości literowych, możliwe jest podzielenie niektórych słów na dwie części, tak aby miały one równe wartości.

Na przykład, „wordsplit” można podzielić na dwie części, takie jak: ordsl wpit, ponieważ o + r + d + s + l = w + p + i + t.

Było to wyzwanie postawione nam przez mojego nauczyciela informatyki - to najwyraźniej stare wyzwanie Lionhead Studios. Rozwiązałem go w Pythonie i wkrótce opublikuję moją odpowiedź.

Wyzwanie: Najkrótszy program, który może wymienić wszystkie możliwe podziały, które mają równe wyniki. Zauważ, że musi zawierać tylko jeden dla każdej grupy liter - na przykład ordsl wpit jest taki sam, jak rdosl wtip. Łatwiej jest je wymienić w kolejności, w jakiej występują w słowie.

Premia:

  • Jeśli zaznaczysz pary, w których oba słowa są poprawnymi słowami angielskimi (lub pewna permutacja liter), użyj jakiejś listy słów. (Można to zrobić, umieszczając gwiazdkę obok każdej innej metody, ale wyjaśnij to.)
  • Dodanie opcji usuwania duplikatów (nie powinno to być domyślne).
  • Obsługuje więcej niż dwa podziały, na przykład trzy, cztery lub nawet n-kierunkowe.
Thomas O
źródło
Czy program musi obsługiwać wprowadzanie różnych liter? A jeśli tak, to czy może odrzucić przypadek wyjścia?
Nemo157,
@ Nemo157 Może ignorować wielkość liter i nie musi zachowywać jej na wydruku.
Thomas O
Czy program może wypisać dodatkowe elementy, o ile żądana część danych wyjściowych jest zrozumiała dla człowieka?
JB
@JB Tak, może.
Thomas O
ok, poprawię tego Perla wtedy;) Dzięki
JB

Odpowiedzi:

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

Uruchom z perl -nE '<code goes here>'. To „n” jest liczone w rozmiarze kodu.

Odpowiedzi:

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

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

  say ""
}

Z komentarzami i nazwami zmiennych:

# 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 ""
}

Niektóre z zastosowanych sztuczek:

  • 1..1<<@_obejmuje ten sam zakres bitów co 0..(1<<@_)-1, ale jest krótszy. (zauważ, że rozważanie problemu z większej odległości, w tym wielokrotne granice zasięgu i tak nie spowodowałoby błędnego wyniku)
  • $ left_range i $ right_range nie są resetowane do rzeczywistego zera numerycznego „0”: ponieważ po prostu gromadzimy je i porównujemy na końcu, wszystko, czego potrzebujemy, to zacząć od tej samej wartości.
  • odejmowanie 64-ord$_[$_]zamiast dodawania ord$_[$_]-64wygrywa niewidzialny znak: ponieważ kończy się na separatorze, czyni to miejsce przed forzbędnym.
  • Perl pozwala na przypisanie do zmiennej ustalonej przez potrójnego operatora warunkowego: cond ? var1 : var2 = new_value.
  • wyrażenia boolowskie połączone łańcuchem &&i ||są używane zamiast odpowiednich warunków warunkowych.
  • $l-$r jest krótszy niż $l!=$r
  • wyświetli znak nowej linii nawet w przypadku podziałów, które się nie równoważą. Puste linie są zgodne z zasadami! Zapytałam!
JB
źródło
Chcesz wyjaśnić tym z nas, którzy nie mówią hałas z linii? Wygląda na to, że używasz binarnej maski podobnej do mojej, i widzę, że 64 oznacza „@” = „A” - 1, a potem jestem prawie zagubiony.
dmckee --- były moderator kociak
Czy ta edycja jest lepsza?
JB
Miły. Muszę pomyśleć o skorzystaniu z dodawania każdej liczby po lewej lub po prawej stronie sumy. Powinno być oczywiste, ale mi tego brakowało.
dmckee --- były moderator kociak
3

J (109)

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

Dane wyjściowe dla wordsplit:

┌─────┬─────┐
Orwlorw │dipst│
├─────┼─────┤
Ildiltw│oprs │
├─────┼─────┤
│iptw │dlors│
├─────┼─────┤
│dlors│iptw │
├─────┼─────┤
│oprs │diltw│
├─────┼─────┤
Ipdipst│lorw │
└─────┴─────┘

Wyjaśnienie:

  • 1!:1[1: przeczytaj wiersz ze standardowego wejścia
  • ([{~(i.@!A.i.)@#): uzyskaj wszystkie permutacje
  • "1: dla każdej permutacji:
  • (96-~a.&i.): uzyskaj wyniki dla liter
  • }.@(split~&.>i.@#@>)@<: podziel każdą permutację wyników na każdej możliwej przestrzeni, z wyjątkiem przed pierwszą i po ostatniej liczbie
  • >(>@(=/@:(+/"1&>)&.>)#[): sprawdź, które kombinacje mają pasujące połówki, i wybierz je
  • {&a.@(96&+)&.>: zamień wyniki z powrotem na litery
  • ~.(/:{[): usuń trywialne odmiany (np. ordsl wpiti ordsl wpti)
marinus
źródło
Niektóre z twoich odpowiedzi są duplikatami.
DavidC
@DavidCarraher: Cóż, albo jestem ślepy, albo ten nie jest, ani moje ostatnie odpowiedzi. Nigdy celowo nie kopiowałem odpowiedzi innych ludzi, chociaż oczywiście możesz mieć rację, czasami pisałem tutaj, kiedy byłem pijany i nie pamiętałem, dopóki nie otrzymałem wielu głosów negatywnych i okazało się, że przesłałem coś, co nawet nie było blisko do poprawnego. Jeśli widziałeś mnie źle zachowującego się, może zostaw komentarz w miejscu, w którym źle się zachowuję, a następnie usunę wszelkie obraźliwe odpowiedzi; a może pochwalić je, bo po to są głosy przegłosowane.
marinus
Nie było żadnych drobiazgów. Chciałem po prostu na przykład powiedzieć, że twoja pierwsza odpowiedź {{lorw "," dipst "} jest duplikatem twojej ostatecznej odpowiedzi {{dipst", "lorw"}. Tylko kolejność słów jest inna.
DavidC,
@DavidCarraher: ups: PI myślał, że masz na myśli, że skopiowałem czyjąś odpowiedź ... w każdym razie to pytanie mówi (jeśli odpowiednio ją zinterpretowałem), aby usunąć duplikaty, w których poszczególne części są po prostu wzajemnymi permutacjami, ale nie do usunięcia te, w których kolejność części jest inna, tj. jeśli {a,bc}już została znaleziona, do usunięcia, {a,cb}ale nie do usunięcia {bc,a}. (I oczywiście nie obrażam się, gdybym faktycznie / miał / zduplikował czyjąś odpowiedź, wolałbym ją, gdyby ktoś to zauważył.)
marinus
Wydajesz się mieć rację. Instrukcje mówią, że można zignorować kolejność słów („Pamiętaj, że musi zawierać tylko jeden dla każdej grupy liter”), ale nie wymagają tego. Może mi to uratować kilka postaci. Dzięki.
DavidC,
2

c99 - 379 niezbędnych znaków

#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);}}}

Podejście jest dość oczywiste. Istnieje funkcja, która sumuje słowa według maski i ta, która drukuje je również według maski. Wejście ze standardowego wejścia. Jedną z osobliwości jest to, że procedura drukowania wstawia spacje na litery, które nie znajdują się w masce. Do oddzielenia grup służy karta.

Nie robię żadnego z przedmiotów bonusowych, ani nie jest łatwo przekonwertować je na wsparcie.

Czytelne i skomentowane:

#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) */
  }
}

Uprawomocnienie

 $ 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 --- były kot moderator
źródło
1

Ruby: 125 znaków

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

Przykładowy przebieg:

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"]]
człowiek w pracy
źródło
1

Mathematica 123 111

Wyszukuje wszystkie podzbiory słowa, które mają 1/2 „Total ASCII” wyrazu d. Następnie znajduje uzupełnienia tych podzbiorów.

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
źródło
1

J, 66 znaków

Za pomocą cyfr liczb base2 wybierz każdy możliwy podzbiór.

   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
źródło
0

Moje rozwiązanie jest poniżej. Jego rozmiar jest prawie anty-golfowy, ale działa bardzo dobrze. Obsługuje podział n-kierunkowy (chociaż czas obliczeniowy staje się bardzo długi dla więcej niż około 3 podziałów) i obsługuje usuwanie duplikatów.

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

Przykładowe dane wyjściowe:

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
źródło
1
Moim zdaniem odpowiedzi, które wprawdzie podejmują zerową próbę osiągnięcia celu pierwotnego pytania (zwięzłość kodu), są w zasadzie nie na temat. Przyznajesz, że ta odpowiedź nie ma związku z golfem kodowym, więc zamiast pisać jako odpowiedź, sugeruję zamieszczenie jej gdzie indziej i umieszczenie linku do niej w komentarzu do pytania.
Jeff Swensen
2
@Sugerman: To implementacja referencyjna, a nie próba wygrania gry. Wolę implementacje referencyjne jako odpowiedzi niż zajmowanie miejsca na górze strony i wolę je na miejscu, aby wyeliminować ryzyko gnicia linków.
dmckee --- były moderator kociąt
@Sugerman: Dlaczego go nie przesłać? To jest lepsze niż nic. To może być zminimalizowane, ale po co się męczyć - Nie mogę przyjąć moje własne pytanie (dobrze, ja mogę , ale to nie jest w duchu niego.)
Thomas O
Ponieważ u podstawy jest to strona pytań i odpowiedzi. Coś, co nie jest zamierzone jako odpowiedź, nie powinno być publikowane jako takie.
Jeff Swensen
1
Jak powiedziałem w moim pierwszym komentarzu, odsyłam do niego w komentarzu do pytania lub ponieważ jesteś właścicielem pytania, edytuj tam link. Nie ma też nic złego w przesłaniu odpowiedzi na własne pytanie, o ile nie akceptujesz automatycznie swojej odpowiedzi bez uwzględnienia wszystkich innych (i wyników głosowania).
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

dane wejściowe muszą być pisane wielkimi literami:

~$ lua wordsplit.lua 
>WORDSPLIT
WDLIT   ORSP
DSPIT   WORL
WPIT    ORDSL
mniip
źródło
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

a tutaj wersja n-split ze 182 bajtami bez duplikatów:

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

Dane wejściowe to np .:

3, 'wordsplit'
Daniel
źródło