fish_solve.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdint.h>

using namespace std;

int tbl1[16] = {9, 240, 193, 169, 186, 195, 141, 128, 161, 69, 210, 242, 3, 200, 152, 183};
int tbl2[16] = {218, 218, 238, 202, 208, 137, 128, 90, 199, 249, 162, 67, 79, 90, 82, 253};

int8_t dp[16][1 << 16][1200];
vector<vector<vector<int8_t> > > next_j;

int solve(int prv, int bitmask, int sum) {
  int i = __builtin_popcount(bitmask);
  if (i == 16) {
      sum += abs(tbl1[prv] - tbl1[0]);
      sum += abs(tbl2[prv] - tbl2[0]);
      if (sum == 0x470) {
        cout << "SICE" << " " << bitmask << " " << prv << endl;
        return 1;
      }
  }
  if(dp[prv][bitmask][sum] != -1) return dp[prv][bitmask][sum];

  int ans = 0;
  for(int j = 0; j < 16; j++) {
    if((bitmask & (1 << j)) == 0) {
      int new_sum = sum + abs(tbl1[j] - tbl1[prv]) + abs(tbl2[j] - tbl2[prv]);
      if(new_sum > 0x470) continue;
      ans = solve(j, bitmask | (1 << j), new_sum);
      if(ans) {
        next_j[prv][bitmask][sum] = j;
        break;
      }
    }
  }

  dp[prv][bitmask][sum] = ans;
  return ans;
}

int main() {
  next_j.resize(16);
  for(int j = 0; j < 16; j++) {
    next_j[j].resize(1 << 16);
    for(int k = 0; k < (1 << 16); k++) {
    next_j[j][k].resize(1200);
      for(int l = 0; l < 1200; l++) {
        dp[j][k][l] = -1;
      }
    }
  }

  cout << solve(9, (1 << 0) | (1 << 9), abs(tbl1[0] - tbl1[9]) + abs(tbl2[0] - tbl2[9])) << endl;

  int prv = 9;
  int sum = abs(tbl1[0] - tbl1[9]) + abs(tbl2[0] - tbl2[9]);
  int bitmask = (1 << 0) | (1 << 9);
  cout << "0 9 ";
  while(sum != 0x470) {
    int j = next_j[prv][bitmask][sum];
    cout << j << " ";
    sum += abs(tbl1[j] - tbl1[prv]) + abs(tbl2[j] - tbl2[prv]);
    bitmask |= (1 << j);
    prv = j;
  }
  cout << endl;
}

vm_code

  0: hash
  1:
  2-12: INPUT
  input[0] = input[0x12] = 0
  input[1] = 9
  values = 0x00 to 0x0f
  sum of values shuld be 0x470
  values must be unique


  # r0 = inp[0]
  13: 01 01 0a:    mov r0, [0x2]       # r0 = [0x2]

  # r1 = inp[16]
  16: 01 05 08:    mov r1, 0x2
  19: 02 05 3d2:   add r1, [0xf4]      # r1 = 2 + [0xf4]
  1c: 01 05 07:    mov r1, [r1 + 0]    # r1 = [0x12]
  1f: 07 01 05:    cmpandsetne r0, r1    # r0 = r1 != [0x2]
  22: 07 05 00:    cmpandsetne r1, 0x0   # r1 = r1 != 0
  25: 02 01 05:    add r0, r1          # r0 += r1
  28: 01 05 08:    mov r1, 0x2         # r1 = 2
  2b: 02 05 04:    add r1, 0x1         # r1 = 3
  2e: 01 05 07:    mov r1, [r1 + 0]    # r1 = [3]
  31: 07 05 24:    cmpandsetne r1, 0x9   # check inp[1] == 9
  34: 02 01 05:    add r0, r1          # r0 += inp[1] != 9 

  37: 0a 08 01:    jz loopTop r0 # check all 3 conditions
  3a: 00 08:       hlt 0x2

loopTop:
  3c: 01 01 00:    mov r0, 0x0
loop:
  # while r0 < 16
  3f: 01 05 01:    mov r1, r0
  42: 07 05 3d2:   cmpandsetne r1, [0xf4] # 16
  45: 0a e4 05:    jz loop_end r1

  # heapadd 0, INP[r0], r0
  48: 01 05 01:    mov r1, r0
  4b: 02 05 08:    add r1, 0x2
  4e: 0b 00 07 01: heapadd 0x0, [r1 + 0], r0 ; index, key, value

  # r2 = get_tbl1(r0)
  52: 01 05 01:    mov r1, r0
  55: 0e 2d4:      call get_tbl1 # 0xb5
  57: 01 09 05:    mov r2, r1

  # r1 = get_tbl1(r0 + 1)
  5a: 01 05 01:    mov r1, r0
  5d: 02 05 04:    add r1, 0x1
  60: 0e 2d4:      call get_tbl1 # 0xb5

  # hash += abs_diff(get_tbl1(r0 + 1), get_tbl1(r0))
  62: 0e 360:      call abs_diff # 0xd8
  64: 02 02 05:    add [0x0], r1

  # get_tbl2(r0)
  67: 01 05 01:    mov r1, r0
  6a: 0e 314:      call get_tbl2 # 0xc5

  # get_tbl2(r0 + 1)
  6c: 01 09 05:    mov r2, r1
  6f: 01 05 01:    mov r1, r0
  72: 02 05 04:    add r1, 0x1
  75: 0e 314:      call get_tbl2 #0xc5

  ; hash += abs_diff(get_tbl2(r0), get_tbl2(r0 + 1))
  77: 0e 360:      call abs_diff
  79: 02 02 05:    add [0x0], r1
  
  ; r0++
  7c: 02 01 04:    add r0, 0x1
  7f: 09 3fef8 01: jmp loop #0x3f

loop_end:
  # assert hash == 0x470
  81: 01 01 3d6:   mov r0, [0xf5] # 0x470
  84: 01 05 02:    mov r1, [0x0]
  87: 07 01 05:    cmpandsetne r0, r1
  8a: 0a 08 01:    jz good_hash r0 # 0x8f
  8d: 00 04:       hlt 0x1
  
good_hash:
# r0 = 1
  8f: 01 01 04:    mov r0, 0x1
  92: 0c 05 09 00: heapremove r1, r2, 0x0 ; dstKey, dstValue, index . key collisions are LIFO

loop2: ; check distinc
	# while r0 != 16
  # r1 is previous key
  96: 01 0d 01:    mov r3, r0
  99: 07 0d 3d2:   cmpandsetne r3, [0xf4] # 16
  9c: 0a 50 0d:    jz 0xb3 r3
  
  # r1 != r2
  9f: 0c 09 0d 00: heapremove r2, r3, 0x0
  a3: 07 05 09:    cmpandsetne r1, r2
  a6: 0a 20 05:    jz 0xb1 r1
  
  a9: 01 05 09:    mov r1, r2
  
  # r0++
  ac: 02 01 04:    add r0, 0x1
  af: 09 3ff94 00: jmp loop2 # 0x96 
  b1: 00 0c:       hlt 0x3
loop2_end:
  b3: 00 00:       hlt 0x0 ; good end


; return TABLE[INP[r1] * 2]
get_tbl1:
  b5: 02 05 08:    add r1, 0x2
  b8: 01 05 07:    mov r1, [r1 + 0]
  bb: 03 05 08:    mult r1, 0x2
  be: 02 05 3d8:   add r1, TABLE # 0xf6
  c1: 01 05 07:    mov r1, [r1 + 0]
  c4: 0f:          ret 

; return TABLE[INP[r1] * 2 + 1]
get_tbl2:
  c5: 02 05 08:    add r1, 0x2
  c8: 01 05 07:    mov r1, [r1 + 0]
  cb: 03 05 08:    mult r1, 0x2
  ce: 02 05 04:    add r1, 0x1
  d1: 02 05 3d8:   add r1, TABLE # 0xf6
  d4: 01 05 07:    mov r1, [r1 + 0]
  d7: 0f:          ret 


; r1 = r2 - r1
; r2 = (r1 & 0xffff) & 0x8000
; if r1 < 0 then r1 = -r1;
abs_diff:
  d8: 08 05 05:    neg r1, r1
  db: 02 05 09:    add r1, r2
  de: 0d 05 05:    mov16 r1, r1
  e1: 01 09 05:    mov r2, r1
  e4: 04 09 20000: and r2, 0x8000
  e7: 07 09 00:    cmpandsetne r2, 0x0
  ea: 0a 18 09:    jz 0xf3 r2
  ed: 08 05 05:    neg r1, r1
  f0: 0d 05 05:    mov16 r1, r1
  f3: 0f:          ret 

  f4:              db 0x10 
  f5:              db 0x470 
TABLE:
  f6:              db 0x09
  f7:              db 0xda
  f8:              db 0xf0
  f9:              db 0xda 
  fa:              db 0xc1 
  fb:              db 0xee 
  fc:              db 0xa9 
  fd:              db 0xca 
  fe:              db 0xba 
  ff:              db 0xd0 
  100:             db 0xc3 
  101:             db 0x89 
  102:             db 0x8d 
  103:             db 0x80 
  104:             db 0x80 
  105:             db 0x5a 
  106:             db 0xa1 
  107:             db 0xc7 
  108:             db 0x45 
  109:             db 0xf9 
  10a:             db 0xd2 
  10b:             db 0xa2 
  10c:             db 0xf2 
  10d:             db 0x43 
  10e: 03 4f c8:   mult [r3 + 4], 0x32
  111:             db 0x5a 
  112:             db 0x98 
  113:             db 0x52 
  114:             db 0xb7 
  115:             db 0xfd