Skip to content

Instantly share code, notes, and snippets.

@sampritipanda

sampritipanda/fish_solve.cpp

Last active April 19, 2020 21:07
Show Gist options
  • Save sampritipanda/bd992d0b6fdff1b0e241fdc1083d1a37 to your computer and use it in GitHub Desktop.
Save sampritipanda/bd992d0b6fdff1b0e241fdc1083d1a37 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
}
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment