개시하다

Step1에서는 최소한의 클립만 가져옵니다.하지만 루비 버전의 문제는 정규화가 2초 가까이 걸리는데 너무 느리기 때문에 우선 루비 버전에서 조금 더 좋은 가지치기를 도입해 보도록 하겠습니다.정규화란 독립용어에 대한 참조저번 보도라는 뜻이다.
소스 코드는 아래에 두십시오.
https://github.com/kaityo256/minlex

방침.

지난번에 트렁크가 완성되기 전에 나뭇가지를 전혀 다듬지 않았다.하지만 그 전에 나뭇가지를 많이 잘라도 돼요.번호는 81자리 숫자로 표시할 수 있으며 가장 작은 숫자를 찾는 패턴은 정규화되었다.따라서 어느 줄이 맨 위로 올라갈 수 있는지부터 고려해야 한다.

칸막이 교환 나뭇가지 자르기

아래의 그림을 보세요.

각 분야에 주의하다.상자마다 줄이 바뀔 수 있으니 줄마다 세 개로 나누어 힌트를 몇 개씩 고려해 보자.맨 위에 있는 줄에 눈을 돌리면(2,1,0).그렇다면 이게 맨 위에 올라가면 정규화 후 힌트가 가장'우측에 기대는'것이기 때문에(0,1,2)의 모델이어야 한다.
마찬가지로 두 번째 줄에 착안하면 두 번째 줄이 맨 위에 도달하면 규범화 모드의 알림 설정은 (0, 0, 2)이어야 한다.여기에 제시된 구성 모드는 (0,1,2)의 경우와 (0,0,2)의 경우 어떤 숫자를 할당하든 (0,0,2)의 값이 작아집니다.따라서 이 순간 맨 위 행은 맨 위로 올라가지 않는다.
그럼 전체 9행에 대해 이걸 진행하면 가장 작은 힌트 도안은(0,0,2)입니다.여기에 (0, 0, 2) 힌트 패턴이 포함되지 않은 상자 행은 맨 위로 올라가지 않습니다.이 예에서 상자행의 교체 6개 모델 중 맨 위에 있는 상자행이 맨 위에 있는 것을 확정했기 때문에 조사해야 할 모델은 2개 모델로 바뀌었다.
물론 전치도 고려해야 한다.따라서 전치 전과 전치 후의 각 모델에 대해 6개 모델을 조사하고 어느 상자가 맨 위에 도달할 수 있는지 조사하며 가장 작은 제시 모델을 조사한다.그 다음에 그 알림 모드가 있는 상자를 제외하고는 돌려서 가지를 자르지 않습니다.

열 바꾸기

그럼 맨 위에 있는 상자는 확실합니다.다음은 상자 열의 정렬입니다.앞의 예라면 맨 위에 있는 상자를 그대로 맨 위에 앉는 것이 가장 작은 패턴이다.이때 맨 위 행의 프롬프트 모드는 (0, 2, 0)입니다.이 숫자를 가능한 한 오른쪽으로 하기 위해서, 반드시 상자열을 바꾸어야 한다.그 도형이 이미 (0,0,2)인 것을 알기 때문에 그 이외의 도형에 대해서는 돌아가지 않고 나뭇가지를 잘라낼 수 있다.

첫 상자 줄 안의 줄 교체

상자 단위의 교체가 끝난 후, 다음은 상자 안의 줄의 교체입니다.헤드박스당 행의 프롬프트 수가 (2,1,0),(0,2,0),(2,0,1)이므로 이 시각 두 번째 행이 맨 위에 도달하도록 결정됩니다.그러나 동일한 프롬프트 모드의 행이 여러 개 있는 경우도 있으므로 먼저 6개 모드를 모두 완료하고 최소 프롬프트 모드와 일치하는 경우에만 복귀할 수 있습니다.

이루어지다

나뭇가지를 더 다듬을 수 있지만 일단 여기에 설치해 두자.

칸막이 교환 나뭇가지 자르기

우선, 첫 번째 가지치기를 할 때 필요한 것은 번호 모드를 제시할 때 그 헤드박스의 최소 알림 모드를 되돌려 주는 방법이다.데이터가 배열되어 있기 때문에 최초의 27개를 9개의 슬라이스로 나누고 3개의 슬라이스로 나누어 제시수의 배열을 한 다음에 정렬할 수 있다.이렇게 되겠지.

def headbox_sorted_index(s)
  sh = s[0..26].each_slice(9).to_a
  sh.map do |shi|
    sa = shi.each_slice(3).to_a
    a2 = sa.map do |ai|
      ai.inject(0) {|sum,v| v!=0 ? sum + 1: sum}
    end.sort
    a2
  end.min
end

이 방법을 사용하면 우선 가능한 12개 모드에 대해 이 헤드박스의 인덱스를 검사하고 최소값hb_min을 찾습니다.그리고 최소치의 헤드박스 패턴을 제외하고는 튕김을 통해 나뭇가지를 잘라낸다.

def search(s)
  a = []
  sa = s.each_slice(27).to_a
  [0,1,2].permutation do |ai|
    a.push sa[ai[0]] + sa[ai[1]] + sa[ai[2]]
  end
  sa = transpose(s).each_slice(27).to_a
  [0,1,2].permutation do |ai|
    a.push sa[ai[0]] + sa[ai[1]] + sa[ai[2]]
  end
  hb_min = a.map{|v| headbox_sorted_index(v)}.min
  a.each do |si|
    next if headbox_sorted_index(si) > hb_min
    perm_cbox(si,hb_min)
  end
end

나중에 사용하기 위해 최소 도안hb_min을 매개 변수로 교부합니다.

박스 바뀐 가지치기

다음은 상자 열 교체에 관한 나뭇가지 가위입니다.방금 힌트 모드(0,2,0)부터 (0,0,2)까지 정렬된 것을 인덱스로 하였으나, 이번에는 정렬되지 않은 것을 인덱스로 하였으며, 방금 구한 최소 힌트 도안(0,0,2)과 일치하는 것만 통과하였다.
그래서 이번에는 색인을 정렬하지 않는 방법을 만들었다.

def headbox_index(s)
  sh = s[0..26].each_slice(9).to_a
  sh.map do |shi|
    sa = shi.each_slice(3).to_a
    a2 = sa.map do |ai|
      ai.inject(0) {|sum,v| v!=0 ? sum + 1: sum}
    end
    a2
  end.min
end

이 글을 쓴 후에 나는'아, 정렬 여부를 매개 변수에 맡겼으면 좋겠다'는 것을 깨달았지만 귀찮아서 그냥 두었다(이후에 소개한 C++판에 그걸 설치했다).
이것을 사용하면 납품의 최소 모델hb_min과 일치하는 모델만 통과하면 됩니다.

def perm_cbox(s,hb_min)
  st = transpose(s)
  sa = st.each_slice(27).to_a
  [0,1,2].permutation do |ai|
    si = sa[ai[0]] + sa[ai[1]] + sa[ai[2]]
    si = transpose(si)
    next if headbox_index(si) > hb_min
    perm_toprbox(si,hb_min)
  end
end

다음에도 써야 하니까 hb_min를 매개 변수에 맡겼어요.

첫 번째 상자의 줄 교체

상자 줄과 열의 교환이 끝났고, 이어서 상자 안의 줄의 교환을 진행한다.나는 이미 (0,0,2) 힌트 모드가 있는 줄을 맨 위에 놓으면 된다는 것을 알고 있다. 그것만 통과하면 된다.구체적으로 말하면 먼저'맨 위의 줄의 알림 모드'의 함수headline_index를 되돌릴 준비를 한다.

def headbox_index(s)
  sh = s[0..26].each_slice(9).to_a
  sh.map do |shi|
    sa = shi.each_slice(3).to_a
    a2 = sa.map do |ai|
      ai.inject(0) {|sum,v| v!=0 ? sum + 1: sum}
    end
    a2
  end.min
end

아까부터 계속 비슷한 방법을 쓰니까 더 예쁜 방법이 있을 것 같아서 신경 쓰지 말고 계속 전진하세요.
이 맨 위의 제시 도안을 되돌려 주는 함수를 사용하면 아래처럼 나뭇가지를 잘라낼 수 있다.

def perm_toprbox(s,hb_min)
  sh,sm,sb = s.each_slice(27).to_a
  sa = sh.each_slice(9).to_a
  [0,1,2].permutation do |ai|
    si = sa[ai[0]] + sa[ai[1]] + sa[ai[2]]
    si = si + sm + sb
    next if headline_index(si) > hb_min
    perm_columns(si)
  end
end

뭐, 최소 힌트 모드에 맞게 맨 위로 올라갈 때만 통과할 수 있다.

결실

여기에 실시된 결과는 다시 기준을 얻으려고 한다.

$ time ruby array.rb
207005000000340000150000009005000001040000320000016500000002084700000010010580000
000000012000034005006007300001300007053080000080000100010005090200100000700400030
OK
ruby array.rb  0.11s user 0.01s system 94% cpu 0.132 total

오, 나뭇가지를 추가로 자르기 전에 1.71초였기 때문에 10배 앞당겼어요.

총결산

1단계에서는'톱27'에 착안해 나뭇가지를 다듬었지만,'톱9'에 착안해 나뭇가지를 다듬었더니 나뭇가지가 비교적 말라 더 빨라졌다.마찬가지로'18위'에 착안해 나뭇가지를 잘라낼 수 있을지 없을지...이렇게 생각하면 사실 첫 줄과 관계가 있어 귀찮다.관심 있는 사람은 고려를 받고 싶다.
이어서셋째.