DouKaku?beta

challenge 文字列の均等分割 

一行の文字列を指定した数の行にできるだけ文字数が均等になるように分割してください．
ただし，除算や剰余算を使わないで書いてみてください．

sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"

divid 4 sample =>
 "ゆめよりもはかなき世のなかを"
 "なげきわびつゝあかしくらすほ"
 "どに四月十よひにもなりぬれ"
 "ば木のしたくらがりもてゆく"

divid 5 sample => 
 "ゆめよりもはかなき世の"
 "なかをなげきわびつゝあ"
 "かしくらすほどに四月十"
 "よひにもなりぬれば木の"
 "したくらがりもてゆく"

divid 6 sample => 
 "ゆめよりもはかなき"
 "世のなかをなげきわ"
 "びつゝあかしくらす"
 "ほどに四月十よひに"
 "もなりぬれば木のし"
 "たくらがりもてゆく"

この問題は、除算だけでははく算術演算とか、文字列の長さをstrlenの類いで測るとかをしなくても、多分書けるのではないかと思います。

post comment

Posted feedbacks - Flatten

Nested Hidden 
「なるべく均等」にというのは
■■■■
■■■■
■■
ではなく
■■■■
■■■
■■■
にすること、という意味だと思ってかまわないですか？
（最長の行と最短の行の差が1文字以内で下の行は上の行以下の長さ、と定式化できる？）

つまりはこういうことでしょうか．
割り算を使わないという意図がいまいちくみ取れませんでした．すいません．
#答えは2byte文字オンリーを仮定しています．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
    int m = atoi(argv[1]);
    const char *s = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく";
    int n = strlen(s) / 2;
    int lineLen = 0;
    int i, j;
    while (n >= m) {
        lineLen++;
        n -= m;
    }
    for (i = 0; i < m; i++) {
        for (j = 0; j < lineLen; j++) {
            putchar(*s++);
            putchar(*s++);
        }
        if (n > 0) {
            putchar(*s++);
            putchar(*s++);
            n--;
        }
        putchar('\n');
    }
    return 0;
};


昼休みの時間にさくっと書いてみる。
割り算とほぼ同等なことをやってるあたりがダメダメだなぁ。

以下出力結果

dev4
ゆめよりもはかなき世のなかを
なげきわびつゝあかしくらすほ
どに四月十よひにもなりぬれ
ば木のしたくらがりもてゆく
dev5
ゆめよりもはかなき世の
なかをなげきわびつゝあ
かしくらすほどに四月十
よひにもなりぬれば木の
したくらがりもてゆく
dev6
ゆめよりもはかなき
世のなかをなげきわ
びつゝあかしくらす
ほどに四月十よひに
もなりぬれば木のし
たくらがりもてゆく
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#-*- coding: utf-8 -*-

def dev(s,num):
    tempCount = [0]*num
    outStr = [""]*num
    i = 0
    for j in xrange(len(s)):
        tempCount[i] += 1
        i = i+1
        if i == num:
            i=0

    for x in xrange(num):
        outStr[x] = s[:tempCount[x]]
        s = s[tempCount[x]:]
    return outStr

#配列をそのままプリントするとユニコードがうまく表示されないので
def printArray(array):
    for x in array:
        print x
 
sample = u"ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"
print "dev4"
printArray(dev(sample,4))
print "dev5"
printArray(dev(sample,5))
print "dev6"
printArray(dev(sample,6))

文字列の長さ分'1'を並べたリストをn要素ごとに分割(余りは0fill)し、i番目の要素を合計するとそれがi行目の文字数になる。

gosh> (define *sample*
  "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく")
*sample*
gosh> (divid 4 *sample*)
("ゆめよりもはかなき世のなかを" "なげきわびつゝあかしくらすほ" "どに四月十よひにもなりぬれ" "ば木のしたくらがりもてゆく")
gosh> (divid 5 *sample*)
("ゆめよりもはかなき世の" "なかをなげきわびつゝあ" "かしくらすほどに四月十" "よひにもなりぬれば木の" "したくらがりもてゆく")
gosh> (divid 6 *sample*)
("ゆめよりもはかなき" "世のなかをなげきわ" "びつゝあかしくらす" "ほどに四月十よひに" "もなりぬれば木のし" "たくらがりもてゆく") 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
(use gauche.sequence)
(use util.list)
(use srfi-13)

(define (divid n str)
  (values-ref
   (map-accum (lambda (n s) (values (string-take s n) (string-drop s n)))
              str
              (apply map + (slices (make-list (string-length str) 1) n #t 0)))
   0))


ジュースを複数のグラスに注ぎ分ける時と同じような考え方です。
投稿間際に確認したところ、ところてん さんと同じ手法のようですね。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 入力される値が2byte文字のみと仮定
#module
#deffunc divid str _target, int num
    if (num <= 0) : return

    target = _target
    dim result, num
    count = 0
    repeat strlen(target) >> 1
        result(count) += 2
        count++
        if(count == num) : count = 0
    loop
    count = 0
    repeat num
        mes strmid(target, count, result(cnt))
        count += result(cnt)
    loop
    return
#global
    sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"
    divid sample, 4
    divid sample, 5
    divid sample, 6

はい、まさにその通りの意図です。(例だけだと伝わらないか。。。)


あれログインし忘れた。


昔、8bitCPUでグラフィック画面に直線を書いた方法の応用?

>php divstr.php 7
ゆめよりもはかな
き世のなかをなげ
きわびつゝあかし
くらすほどに四
月十よひにもなり
ぬれば木のしたく
らがりもてゆく
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
<?php
$sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく";

$d=max($argv[1],1);
$l=strlen($sample);
$s=$l;
for($i=0;($c=mb_substr($sample,$i,1))!='';++$i)
{    echo $c;
    for($j=0;$j<strlen($c);++$j)
        $s-=$d;
    if($s<=0)
    {    echo "\n";
        $s+=$l;
    }
}
?>

この問題は、除算だけでははく算術演算とか、文字列の長さをstrlenの類いで測るとかをしなくても、多分書けるのではないかと思います。


0からnumまでの無限リスト(num=4なら0,1,2,3,0,1,2,3...)を作成し、文字列の長さ分takeします。

そのリスト中のnの出現回数を求めると分割後のn個目要素の文字数になります。

ちゅーか、無限リストをライブラリで用意するならcycleとかrepeatくらい提供してほしい・・・ 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def cycle[A](s:Iterable[A]):Stream[A] = {
  def rep[A](s:Stream[A], p:int):Stream[A] = {
    val n = (if(p<s.size){p}else{0})
    Stream.cons(s(n), rep(s, n+1))
  }; rep(s.toStream,0)
}

def divid(num:int, str:String) = {
  val table = (Array.make(num, 0) /: cycle(0 until num).take(str.length)){(r,n) =>
    r(n) = r(n)+1;r
  }
  val result = new Array[String](num)
  (str /: (0 until num)){(s,n) =>
    result(n) = s.substring(0, table(n))
    s.substring(table(n))
  }
  result
}

Javaで書いてみました。 一応String::lengthを使わないことだけ意識しました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.io.IOException;
import java.io.StringReader;

public class Divid {

    public static void main(String[] args) throws IOException{
        int[] n = new int[Integer.parseInt(args[0])];
        String target = args[1];
        for (int i = 0; i < n.length; i++) {
            n[i] = 0;
        }
        int turn = 0;
        StringReader reader = new StringReader(target);
        while(reader.read() != -1){
            n[turn++]++;
            if (turn == n.length)
                turn = 0;
        }
        String v[] = new String[n.length];
        int pos = 0;
        for (int i = 0; i < n.length; i++) {
            v[i] = target.substring(pos, (pos = (pos + n[i])));
            System.out.println(v[i]);
        }
    }
}

文字列分のTrueの後にFalseをいくつかくっつけたリストを作り、nで分割した後transposeして、Trueの分だけ先頭から切り出す。

例えばdivid 3 "abcdefghijk"なら

 bools = [T,T,T,T,T,T,T,T,T,T,T,F,F,F]
 slices = [[T,T,T],[T,T,T],[T,T,T],[T,T,F]]
 transpose = [[T,T,T,T],[T,T,T,T],[T,T,T,F]]

boolsを無限リスト(Fが後ろに無限個付く)にしてもいけるかと思ったけど、無限リストのtransposeは止まらないみたい。そこまで見ないんだから止まってくれても良さそうな気がするけど… 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import Data.List

divid n cs = snd $ mapAccumL taker cs
                 $ transpose
                 $ slices
                 $ bools cs
 where
   slices xs | n > length xs = []
             | otherwise     = (take n xs):(slices $ drop n xs)
   bools cs = (map (const True) cs) ++ (replicate n False)
   taker (c:cs) (True:bs) = let (cs',frag) = (taker cs bs)
                              in (cs', c:frag)
   taker cs _             = (cs, [])

いや、そもそも後ろにFalseをくっつける必要が無かった。takeはリストの方が短いと結果も短くしてくれるのね。(Gaucheのtake*の動作)

1
2
3
4
5
6
7
8
import Data.List

divid n cs = snd $ mapAccumL taker cs $ transpose $ slices cs
 where
   slices [] = []
   slices xs = (take n xs):(slices $ drop n xs)
   taker cs []         = (cs, [])
   taker (c:cs) (b:bs) = let (cs',frag) = (taker cs bs) in (cs', c:frag)

行数以外は数値を使ってません。 もっとよく考えればきれいに書けるかも。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
(defun divid-1 (string n)
  (loop
     with list = (coerce string 'list)
     with list2 = (nthcdr n list)
     for slow on list
     for fast = list2 then (or (nthcdr n fast) list2)
     if (eq list2 fast) collect slow))

(defun divid-2 (string n)
  (loop with list = (divid-1 string n)
     with last = (last list)
     for sublist on (cdr list)
     while (car last)
     do (mapl (lambda (l) (pop (car l))) sublist)
     finally (return (mapcar #'ldiff list (cdr list)))))

(defun divid (string n)
  (mapcar (lambda (l) (format nil "~{~C~}" l)) (divid-2 string n)))

先に何文字で分割するかを計算させてから文字分割しています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Divide {
    public static void main(String[] args) {
        String sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく";
        System.out.println(Arrays.toString(devide(sample, 4)));
        System.out.println(Arrays.toString(devide(sample, 5)));
        System.out.println(Arrays.toString(devide(sample, 6)));
    }
    public static String[] devide(String s, int r) {
        int[] x = new int[r];
        for (int i = 0, j = 0; i < s.length(); i++, j++) {
            if (j >= x.length) j = 0;
            x[j]++;
        }
        List<String> list = new ArrayList<String>(r);
        for (int i = 0; i < x.length; i++) {
            list.add(s.substring(0, x[i]));
            s = s.substring(x[i]);
        }
        return list.toArray(new String[0]);
    }
}


■■■■
■■■■
■■■
の場合に
■■■■
■■■
■■■■
という出力がありなのか
ふと疑問に思ったもので…。


だいたいこんな処理になってます。

divid-1: 分割すべき位置を近似的に見つける
"ゆめよりもはかなき世のなかを...", 4
->
("ゆめよりもはかなき世のなかを..." "をなげきわびつゝあかしくらす..."
 "すほどに四月十よひにもなりぬ..." "ぬれば木のしたくらがりもてゆく"
 "ゆく")

divid-2: 末尾が空になるまでひとつずつずらす
   ("ゆめよりも..." "をなげきわ..." "すほどに四..." "ぬれば木の..." "ゆく")
-> ("ゆめよりも..." "なげきわ..." "ほどに四..." "れば木の..." "く")
-> ("ゆめよりも..." "なげきわ..." "どに四..." "ば木の..." "")

divid: 重複部分を削る
("ゆめよりもはかなき世のなかをなげき..." "なげきわびつゝあかしくらすほどに四..."
 "どに四月十よひにもなりぬれば木のし..." "ば木のしたくらがりもてゆく" "")
-> 
("ゆめよりもはかなき世のなかを" "なげきわびつゝあかしくらすほ"
 "どに四月十よひにもなりぬれ" "ば木のしたくらがりもてゆく")

正規表現を使いました。

countは0以上の無限リストを作成する命令で、0以上の各整数iについて「『i文字またはi+1文字』のブロックがn個ある」という正規表現を作ってマッチを試みます。マッチすればグループ分けをreturn。greedyなので前半のグループが長い方、後半のグループが短い方になります。

1
2
3
4
5
6
7
8
def divid(n, s):
    import re
    from itertools import count
    for i in count():
        pat = "^%s$" % "(.?.{%d})" % i * n
        m = re.match(pat, s)
        if m:
            return m.groups()

算術演算もstrlenに相当する関数も使ってないよ！(よっぽどうれしかったらしい)


私の用意していたものはshiroさんの解と本質的に同じでした。
slices と taker にも汎用性がありそうなのでトップレベルでの定義にしてあります。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import Data.List
import qualified System.IO.UTF8 as U

divid :: Int -> [a] -> [[a]]
divid n xs 
  = snd $ mapAccumL ((swap .) . flip splitWith) xs $  transpose $ slices n xs

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

splitWith :: [b] -> [a] -> ([a],[a])
splitWith _  [] = ([],[])
splitWith [] xs = ([],xs)
splitWith (x:xs) (y:ys) = case splitWith xs ys of (zs,ws) -> (y:zs,ws)

slices :: Int -> [a] -> [[a]]
slices n = unfoldr phi
  where 
    phi [] = Nothing
    phi xs = Just $ splitAt n xs

括弧が抜けてました…

1
2
- pat = "^%s$" % "(.?.{%d})" % i * n
+ pat = "^%s$" % ("(.?.{%d})" % i * n)


5 行目は、
pat = "^%s$" % ("(.?.{%d})" % i * n)
のように括弧が必要だったりしませんか？

修正済でしたね…。すみません。


Squeak Samlltalk で。

shiro さんの #4217 の考え方をお借りして。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
| sample divide |
divide := [:sourceStr :numOfLines |
    | stream ones zeros |
    stream := sourceStr readStream.
    ones := (sourceStr as: Array) atAllPut: 1.
    zeros := Array new: numOfLines withAll: 0.
    (ones, zeros groupsOf: numOfLines atATimeCollect: [:group | group]) sum
        collect: [:numOfChars | stream next: numOfChars]].

sample := 'ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく'.

divide value: sample value: 4.
"=> #('ゆめよりもはかなき世のなかを' 'なげきわびつゝあかしくらすほ' 'どに四月十よひにもなりぬれ' 'ば木のしたくらがりもてゆく') "

divide value: sample value: 5.
"=> #('ゆめよりもはかなき世の' 'なかをなげきわびつゝあ' 'かしくらすほどに四月十' 'よひにもなりぬれば木の' 'したくらがりもてゆく') "

divide value: sample value: 6.
"=> #('ゆめよりもはかなき' '世のなかをなげきわ' 'びつゝあかしくらす' 'ほどに四月十よひに' 'もなりぬれば木のし' 'たくらがりもてゆく') "


■■■■
■■■■
■■■
■■■
より
■■■■
■■■
■■■■
■■■
の方が「より均等」に思えてしまう…。

なるほどなるほど。では nongreedy なものを。 
1
2
3
4
function doukaku88(n, s){
  for(var i = 0, m; !(m = s.match(RegExp('^'+ Array(n + 1).join('(.{'+ i +','+ ++i +'}?)') +'$'))););
  return m.slice(1);
}


例えば5分割の場合、以下のように配列を作成後、文字が入っている所に入力文字を当てはめていくようにしました。

"ゆはのげゝら四にれたも"
"めかなきあす月もばくて"
"よなかわかほ十な木らゆ"
"りきをびしどよりのがく"
"も世なつくにひぬしり"

shiroさんと同様のロジックですね。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def strDiv(n,s)
  r = [[]]
  s1 = s.split(//)
  while s1!=[]
    1.upto(n) {|i|
      (r[i-1] ||= []) << s1.shift
    }
  end
  s1 = s.split(//)
  r.each {|i|
    i.each {|j|
      print s1.shift if j
    }
    puts
  }
end


strDiv(5,"ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく")


divid(4, "Perlわかるひとには長いよって思われそうだし、Perlわかんないひとには読めねえよって思われそうだけどいいんだ。ってこれ半角混ぜるとぐじゃぐじゃになるな")
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
use strict;
use warnings;
use utf8;
binmode(STDOUT, ":utf8");

sub divid {
    my $line = shift @_;
    my $str = shift @_;
    my @table;
    my @str_array = split //, $str;
    push @table, [] for 1..$line;
    
    while (@str_array) {
        for (@table) {
            push @$_, (shift @str_array);
        }
    }
    
    for (@table) {
        @$_ = grep { defined $_ } @$_;
    }
    
    @str_array = split //, $str;
    
    for my $array_ref (@table) {
        for (@$array_ref) {
            $_ = shift @str_array;
        }
    }
    
    for (@table) {
        print "\"", join('', grep { defined $_ } @$_), "\"", "\n";
    }
}

divid(4, "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく");

最初に，行数分の文字ずつ(例えば，4分割なら4文字ずつ)与えられた文字列を走査し，[14, 14, 13, 13] のような各行の文字数からなる配列を作ります．次に，配列を走査しつ つ，この文字数ずつ文字列をとって配列の中身を置き換え，出力とします．

% ./divid.rb
divid 4:
["ゆめよりもはかなき世のなかを",
 "なげきわびつゝあかしくらすほ",
 "どに四月十よひにもなりぬれ",
 "ば木のしたくらがりもてゆく"]

divid 5:
["ゆめよりもはかなき世の",
 "なかをなげきわびつゝあ",
 "かしくらすほどに四月十",
 "よひにもなりぬれば木の",
 "したくらがりもてゆく"]

divid 6:
["ゆめよりもはかなき",
 "世のなかをなげきわ",
 "びつゝあかしくらす",
 "ほどに四月十よひに",
 "もなりぬれば木のし",
 "たくらがりもてゆく"]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
require 'pp'
$KCODE='EUC'

class String
  def divid(lines)
    out, x, y = [0] * lines, split(''), nil
    y.times {|i| out[i] += 1 } while (y = x.slice!(0, lines).size) > 0

    rest = self
    out.map! do |len|
      _, ret, rest = *rest.match(/(.{#{len}})(.*)/)
      ret
    end
  end
end

sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"
(4..6).to_a.each do |i|
  puts "divid #{i}:"
  pp sample.divid(i)
  puts
end


例えば3分割なら1, 2, 3, 1, 2, 3, ... という配列を作ってソートし、1が並んでいるインデックスを1列目、
2が並んでいるインデックスを2列目・・・という風に文字列をスライスしています。

1
2
3
4
5
divid <- function(num, sample){
   string <- unlist(strsplit(sample, ""))
   breaks <- sort(rep(1:num, len=length(string)))
   cat(sapply(1:num, function(n)(paste(string[breaks==n], collapse=""))), sep="\n")
}


文字数数えるのが面倒だったので、スライスでn個飛ばしの文字列を作って、それの文字数を使いました。
オフセット数えるのも、面倒なので再帰任せです。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# encoding: utf-8

sample = u"ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"

def divid(str, n, target_list=[]):
  def get_splitted_str(str, n):
    return str[:len(str[::n])]

  if str:
    s = get_splitted_str(str, n)
    return divid(str[len(s):], n-1, target_list+[s])
  else: return target_list

for i in range(4,7):
  print "divid", i
  l = divid(sample, i)
  for line in l:
    print line
  print ""

なるほど。その発想を使ってみました。 cycleは与えられたリストを巡回し続ける無限リストで、zipは短い方に会わせて切り詰めます。

これでも算術演算やstrlenは必要ないですね…正規表現を使うよりは黒魔術っぽさがなくていいかも。

>>> cycle(range(3))
<itertools.cycle object at 0x0270AAA8>
>>> zip(_, "hoge")
[(0, 'h'), (1, 'o'), (2, 'g'), (0, 'e')]

1
2
3
4
5
def divid(n, s):
    from itertools import cycle
    xs = zip(cycle(range(n)), s)
    return ["".join(c for i, c in xs if i == j)
             for j in range(n)]


算術演算も文字列長取得関数も使っていません。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#-*- coding: utf-8 -*-

def divid(n, s):
  s = unicode(s, 'utf-8')
  sl = list(s)
  l = []
  while s:
    l.append(list(s[:n]))
    s = s[n:]

  print '\ndivid %d sample =>' % n
  while l[0]:
    print ' "%s"' % ''.join([a.pop(0) and sl.pop(0) for a in l if a])

sample = 'ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく'

print '"sample = %s"' % sample
divid(4, sample)
divid(5, sample)
divid(6, sample)