태그 보관물: packing

packing

목재 조각 포장 있습니다. 둘 다

두 조각의 나무가 있습니다. 둘 다 직선 몸체와 몸체 아래에 여분의 블록이 있습니다. 0,4,7,9,10 위치에 (0- 인덱싱 된) 위치에 추가 블록이있는 예제 조각 :

XXXXXXXXXXX
X   X  X XX

피스는 th 위치에 블록이 있는지를 나타내는 th 문자 로 01이진 시퀀스 로 표시 될 수 있습니다 . 위의 예는로 표시 될 수 있습니다 .ii10001001011

우리는 두 번째 것을 수직으로 뒤집어서 (그리고 아마도 수평으로 뒤집어서) 두 조각을 모을 수 있습니다. 뒤집기 후에 우리는 두 조각의 높이가 3이되도록 정렬 할 수 있습니다.

Two example pieces:

XXXXXXXXXXX   XXXXXXXX
X   X  X XX     XXX

Second piece flipped vertically and horizontally:

 XXXXXXXXXXX
 X   X  X XX
  XXX
XXXXXXXX

Pieces put together:

 XXXXXXXXXXX
 XXXXX  X XX
XXXXXXXX

이 예에서는 총 너비가 12 블록입니다.

두 조각을 나타내는 입력으로 두 개의 문자열을 수신 하고 높이가 3 인 최소 달성 가능 너비 를 정수로 출력하는 프로그램 또는 함수를 작성해야합니다 .

입력

  • 문자로 구성된 두 문자열 0과 1.
  • 두 문자열 모두 하나 이상의 문자를 포함합니다.
  • 하나의 공백으로 연결된 두 개의 문자열을 수신하도록 선택할 수 있습니다.

산출

  • 달성 가능한 최소 총 너비 인 단일 양의 정수

예

0 0  =>  1

1 0  =>  1

1 1  =>  2

11 111  =>  5

010 0110  =>  5

0010 111  =>  5

00010 11011  =>  6

01010 10101  =>  5

1001 100001  =>  6

1110001100001 1100100101  =>  14

001101010000101 100010110000  =>  16

0010110111100 001011010101001000000  =>  21

0010110111100 001011010101001001100  =>  28

100010100100111101 11100101100010100100000001  =>  27

0010 10111  =>  5

0100 10111  =>  5

0010 11101  =>  5

0100 11101  =>  5

10111 0010  =>  5

10111 0100  =>  5

11101 0010  =>  5

11101 0100  =>  5

이것은 코드 골프이므로 가장 짧은 참가작이 승리합니다.

답변

Pyth, 37 35 34 32 31 바이트

eSX0lM.zff-\1@VhY>eYT*Fm,d_d.z0

줄 바꿈 입력을 분리합니다.

데모 , 테스트 하니스 .

설명:

높은 수준에서 일반 문자열과 반전 문자열의 각 조합에 대해 주어진 위치 수만큼 두 번째 문자열을 왼쪽으로 이동하고 첫 번째 문자열과 겹치는 지 확인합니다. 겹치지 않는 이동량이 발견 될 때까지이 과정이 반복됩니다. 해당 시프트 양이 첫 번째 문자열 길이에 추가되고 결과가 두 번째 문자열 길이와 비교됩니다. 높은 값이 인쇄됩니다.

eSX0lM.zff-\1@VhY>eYT*Fm,d_d.z0

                            .z     The list of the two input strings.
                       m           Map to
                        ,d_d       The pair of each string and its reverse.
                     *F            Take the cartesisan product of those lists.
         f                         Filter those pairs of a first string and a
                                   second string, possibly reversed,
          -\1                      On the absence of the string "1" in
             @V                    The vectorized intersection (intersection
                                   of 0th position, 1st position, etc.) of
               hY                  the first string and
                 >eYT              the second string without the first T elements.
        f                    0     Starting at 0 and counting upwards, find the
                                   lowest T where the result is truthy.
                                   (where anything passes the inner filter)
    lM.z                           Map the input strings to their lengths.
  X0                               Add the above result to the first entry.
eS                                 Take the maximum of the two values and print.

답변

핍 , 72 70 48 바이트

Fp[aRVa]CP[bRVb]L#a+1{I2NI$+plAE:#$+^pp@1.:0}MNl

두 문자열을 명령 행 인수로 사용합니다. 주석이 포함 된 형식 :

                     a, b initialized from cmdline args; l is [] (implicit)
F p [aRVa]CP[bRVb]   For each possible pair p of a/reverse(a) with b/reverse(b):
 L #a+1 {            Loop for each potential offset of bottom piece:
  I 2 NI $+p         If no 2's in the sum of p:
   l AE: # $+ ^p     Append the max width of elements of p to l (see below for explanation)
  p@1 .: 0           Append a 0 to bottom piece
 }
MNl                  The answer is min(l); print it (implicit)

하단 조각이 왼쪽으로 튀어 나와있는 부분 만 계산하므로 상단과 하단 부분을 뒤집어 시도해야합니다. 내부 루프를 통과 할 때마다 합계에 2가 없으면 적합합니다. 그런 다음 하단 부분의 끝에 다른 0을 고정하고 다시 시도하십시오.

   0010
    111
   0121

   0010
   111_
   1120

   0010
  111__
  11110

   0010
 111___
 111010

   0010
111____
1110010

총 너비를 찾기 위해의 요소 p를 문자 목록과 합계로 나눕니다. 길이가 고르지 않은 목록에 대한 항목 별 작업은 더 긴 목록의 길이를 유지하므로이 합계의 길이가 정확히 필요합니다. (단순히 숫자로 합산하는 것은 앞의 0을 제거하기 때문에 분할이 필요 : $+[0101 10] = 111하지만 $+^[0101 10] = [0 1 1 1].)

C:\> pip.py woodPacking.pip 0010 111
5

답변

루비 127 130

이것은 너무 길다 는 것이 밝혀졌습니다 … 🙁

->m,n{[[m,n],[m,n.reverse],[n,m],[n,m.reverse]].map{|u,d|[(0..l=u.size).find{|i|(d.to_i(2)<<i)&u.to_i(2)<1}+d.size,l].max}.min}

테스트 : http://ideone.com/te8XWk

읽을 수있는 루비 : 

def pack_length piece1, piece2
  min_possible_packed_length = [
    min_packed_length(piece1, piece2),
    min_packed_length(piece1, piece2.reverse),
    min_packed_length(piece2, piece1),
    min_packed_length(piece2, piece1.reverse)
  ].min

  min_possible_packed_length
end

def min_packed_length up_piece, down_piece
  x = up_piece.to_i 2
  y = down_piece.to_i 2

  # find the smallest shift for the piece placed down 
  # so that they fit together
  min_packed_shift = (0..up_piece.size).find{|i| (y<<i)&x<1 }

  # min pack length cannot be smaller than any of the 
  # two pieces
  [min_packed_shift + down_piece.size, up_piece.size].max
end

답변

자바 스크립트 ( ES6 ) 160

더 짧게 만들 수 없습니다 …

F=(a,b,c=[...b].reverse(),
K=(a,b,t=a.length)=>{
for(e=i=-1;e&&i++<t;)for(e=j=0;u=b[j];j++)e|=u&a[j+i];
return t<i+j?i+j:t
})=>Math.min(K(a,b),K(a,c),K(b,a),K(c,a))

// test

out=x=>O.innerHTML += x+'\n'

test=[
 ['0', '0', 1],['1', '0', 1],['1', '1', 2],['11', '111', 5]
,['010', '0110', 5],['0010', '111', 5],['0010', '10111', 5]
,['00010', '11011', 6],['01010', '10101', 5],['1001', '100001', 6]
,['1110001100001', '1100100101', 14]
,['001101010000101', '100010110000', 16]
,['0010110111100', '001011010101001000000', 21]
,['0010110111100', '001011010101001001100', 28]
,['100010100100111101', '11100101100010100100000001', 27]
,['0010','10111', 5],['0100','10111', 5]
,['0010','11101', 5],['0100','11101', 5]
,['10111','0010', 5],['10111','0100', 5]
,['11101','0010', 5],['11101','0100', 5]
]

test.forEach(t=>{
  r = F(t[0],t[1]),
  out(
    (r==t[2]?'Ok':'Fail')
    + ' A: '+t[0]+', B: '+t[1]
    + ', Result: '+r + ', Check:  '+t[2])
})
pre { font-size: 10px }
<pre id=O></pre>

스 니펫 확장

답변