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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
module day_09_utils
implicit none
contains
subroutine swap_to_first_positive_integer_from_end(arr, idx)
implicit none
integer, allocatable, intent(inout) :: arr(:)
integer, intent(in) :: idx
integer, allocatable :: temp(:)
integer :: i, res
do i = 0, size(arr) - 1
if(arr(size(arr) - i) > -1) then
arr(idx) = arr(size(arr) - i)
allocate(temp(size(arr) - (i +1)))
temp = arr(1:size(arr) - (i+1))
call move_alloc(temp, arr)
return
end if
end do
end subroutine swap_to_first_positive_integer_from_end
subroutine append_to_integer_array_times(arr, val, times)
implicit none
integer, allocatable, intent(inout) :: arr(:)
integer, intent(in) :: val, times
integer, allocatable :: temp(:)
if(.not. allocated(arr)) then
ERROR STOP 'Array not allocated'
end if
allocate(temp(size(arr) + times))
temp(1:size(arr)) = arr
temp(size(arr) + 1:size(temp)) = val
call move_alloc(temp, arr)
end subroutine append_to_integer_array_times
end module day_09_utils
program day_09
use iso_fortran_env, only: int64
use day_09_utils
implicit none
integer :: io, ios, i, j, block_n, ct, block_start, block_end, space_start, space_end
integer(kind=int64) :: res
character(len=1) :: c
integer, allocatable :: system(:), work(:), done(:)
logical :: is_space, space_block_start
open(newunit=io, file='./day_09_input.txt', status='old', action='read', access='stream')
is_space = .false.
block_n = 0
do
read(io, iostat=ios) c
if (ios /= 0) exit
read(c, *, iostat=ios) i
if(ios /= 0) exit
if (i == 0) then
is_space = .false.
cycle
end if
if (.not. allocated(system)) then
allocate(system(i))
system(1:i) = block_n
is_space = .true.
block_n = block_n + 1
else
if (is_space) then
call append_to_integer_array_times(system, -1, i)
is_space = .false.
else
call append_to_integer_array_times(system, block_n, i)
block_n = block_n + 1
is_space = .true.
end if
end if
end do
allocate(work(size(system)))
work = system
ct = count(work > -1)
outer: do
do i = 1, size(work)
if (i == ct) exit outer ! we are done
if(work(i) < 0) then
call swap_to_first_positive_integer_from_end(work, i)
exit
end if
end do
end do outer
res = 0
do i = 1, size(work)
if(work(i) > -1) then
res = res + ((i-1) * work(i))
else
end if
end do
print *, res
! start_part_2
res = 0
deallocate(work)
allocate(work(size(system)))
work = system
block_n = -1
block_start = -1
block_end = -1
do i = size(work), 1, -1
if(block_n == -1 .and. work(i) /= -1) then
! we are starting a block
block_end = i
block_n = work(i)
if(allocated(done) .and. count(done == block_n) > 0) then
block_n = -1
block_start = -1
block_end = -1
cycle
else if(.not. allocated(done)) then
allocate(done(1))
done(1) = block_n
else
call append_to_integer_array_times(done, block_n, 1)
end if
else if (block_n /= -1 .and. block_n /= work(i)) then
! we are ending the block
block_start = i
! lets try to move the block
space_block_start = .true.
do j = 1, size(work)
if (j > block_start) exit
if(space_block_start .and. work(j) == -1) then
space_start = j
space_block_start = .false.
else if (.not. space_block_start .and. work(j) /= -1) then
space_end = j
space_block_start = .true.
if(space_end - space_start >= block_end - block_start) then
work(space_start:space_start + (block_end - (block_start +1))) = block_n
work(block_start+1:block_end) = -1
exit
end if
space_end = -1
space_start = -1
end if
end do
block_n = work(i)
block_end = i
block_start = -1
end if
end do
do i = 1, size(work)
if(work(i) /= -1) then
res = res + ((i-1) * work(i))
end if
end do
print *, res
end program day_09
|
